dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 56
Текст из файла (страница 56)
В своем начальном состоянии PF спонтанно переходит вначальное состояние автомата PN, заталкивая его стартовый символ Z0 в магазин.2.Для всех состояний q из Q, входов a из Σ (или a = ε) и магазинных символов Y из Γ,δF(q, a, Y) содержит все пары из δN(q, a, Y).3.В дополнение к правилу (2), δF(q, ε, X0) содержит (pf, ε) для каждого состояния q из Q.Докажем, что w ∈ L(PF) тогда и только тогда, когда w ∈ N(PN).*(Достаточность) Нам дано, что (q0, w, Z0) |− (q, ε, ε) для некоторого состояния q. ПоPN*теореме 6.5 можно добавить X0 на дно магазина и заключить, что (q0, w, Z0X0) |−PN(q, ε, X0). Поскольку по правилу 2 у PF есть все переходы PN, можно утверждать также,6.2.
ßÇÛÊÈ ÌÏ-ÀÂÒÎÌÀÒÎÂСтр. 245245*что (q0, w, Z0X0) |− (q, ε, X0). Если эту последовательность переходов собрать вместе сPNначальным и заключительным переходами в соответствии с правилами 1 и 3, то получимследующее.*(p0, w, X0) |− (q0, w, Z0X0) |− (q, ε, X0) |− (pf, ε, ε)PFPF(6.1)PFТаким образом, PF допускает w по заключительному состоянию.(Необходимость) Заметим, что дополнительные переходы по правилам 1 и 3 дают весьмаограниченные возможности для допускания w по заключительному состоянию.
Правило 3должно использоваться только на последнем шаге, и его можно использовать, если магазин PFсодержит лишь X0. Но X0 не появляется нигде в магазине, кроме его дна. Правило 1 используется только на первом шаге, и оно должно использоваться на первом шаге.Таким образом, любое вычисление в автомате PF, допускающее w, должно выглядетькак последовательность (6.1). Более того, середина вычисления (все переходы, кромепервого и последнего) должна также быть вычислением в PN с X0 под магазином. Этообусловлено тем, что, за исключением первого и последнего шагов, PF не может использовать переходы, которые не являются переходами PN, и X0 не может оказаться на вершине магазина (иначе вычисление заканчивалось бы на следующем шаге). Таким обра*зом, (q0, w, Z0) |− (q, ε, ε), и w ∈ N(PN).
PNПример 6.10. Построим МП-автомат, который обрабатывает последовательностислов if и else в С-программе, где i обозначает if, а e — else. Как показано в разделе 5.3.1, в любом префиксе программы количество else не может превышать числа if,поскольку в противном случае слову else нельзя сопоставить предшествующее ему if.Итак, магазинный символ Z используется для подсчета разницы между текущими количествами просмотренных i и e.
Этот простой МП-автомат с единственным состояниемпредставлен диаграммой переходов на рис. 6.5.εНачалоРис. 6.5. МП-автомат, допускающий ошибки if/elseпо пустому магазинуУвидев i, автомат заталкивает Z, а e — выталкивает. Поскольку он начинает с однимZ в магазине, в действительности он следует правилу, что если в магазине Zn, то символов i прочитано на n – 1 больше, чем e. В частности, если магазин пуст, то символов eпрочитано на один больше, чем i, и входная последовательность недопустима в С-прог246Стр. 246ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞрамме. Именно такие цепочки наш МП-автомат PN допускает по пустому магазину. Егоформальное определение имеет следующий вид.PN = ({q}, {i, e}, {Z}, δN, q, Z)Функция δN задается таким образом.1.δN(q, i, Z) = {(q, ZZ)}.
По этому правилу заталкивается Z при i на входе.2.δN(q, e, Z) = {(q, ε)}. Z выталкивается при входе e.εНачалоεεεРис. 6.6. Конструкция МП-автомата, допускающего по заключительномусостоянию и построенного на основе автомата PN (см. рис. 6.5)Теперь на основе PN построим МП-автомат PF, допускающий этот же язык по заключительному состоянию; его диаграмма переходов показана на рис. 6.6.3 Вводим новыеначальное и заключительное состояния p и r, а также используем X0 в качестве маркерадна магазина. Формально автомат PF определяется следующим образом.PF = ({p, q, r}, {i, e}, {Z, X0}, δF, q, Z)Функция δF задается таким образом.1.δF(p, ε, X0) = {(q, ZX0)}.
По этому правилу PF начинает имитировать PN с маркеромдна магазина.2.δF(q, i, Z) = {(q, ZZ)}. Z заталкивается при входе i, как у PN.3.δF(q, e, Z) = {(q, ε)}. Z выталкивается при входе e, как у PN.4.δF(q, e, X0) = {(r, ε)}. PF допускает, когда имитируемый PN опустошает свой магазин.6.2.4.
Îò çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ ê ïóñòîìó ìàãàçèíóТеперь пойдем в обратном направлении: исходя из МП-автомата PF, допускающегоязык L по заключительному состоянию, построим другой МП-автомат PN, который допускает L по пустому магазину. Конструкция проста и представлена на рис. 6.7. Добавляется переход по ε из каждого допускающего состояния автомата PF в новое состояниеp. Находясь в состоянии p, PN опустошает магазин и ничего не прочитывает на входе.3Не обращайте внимания на то, что тут использованы новые состояния p и r, хотя в конструкции теоремы 6.9 указаны p0 и pf. Имена состояний могут быть совершенно произвольными.6.2. ßÇÛÊÈ ÌÏ-ÀÂÒÎÌÀÒÎÂСтр.
247247Таким образом, как только PF приходит в допускающее состояние после прочтения w, PNопустошает свой магазин, также прочитав w.Во избежание имитации случая, когда PF случайно опустошает свой магазин без допуска, PN должен также использовать маркер X0 на дне магазина. Маркер является егостартовым символом и аналогично конструкции теоремы 6.9 PN должен начинать работув новом состоянии p0, единственная функция которого — затолкнуть стартовый символавтомата PF в магазин и перейти в начальное состояние PF. В сжатом виде конструкцияпредставлена на рис.
6.7, а ее формальное описание приводится в следующей теореме.Началоε любой/ ε ε любой/ εεε любой/ εРис. 6.7. PN имитирует PF и опустошает свой магазин тогда и только тогда,когда PF достигает заключительного состоянияТеорема 6.11. Пусть L = L(PF) для некоторого МП-автоматаPF = (Q, Σ, Γ, δF, q0, Z0, F). Тогда существует такой МП-автомат PN, у которого L = N(PN).Доказательство.
Конструкция соответствует рис. 6.7. ПустьPN = (Q U {p0, p}, Σ, Γ U {X0}, δN, p0, X0),где δN определена следующим образом.1.δN(p0, ε, X0) = {(q0, Z0X0)}. Работа начинается с заталкивания стартового символа автомата PF в магазин и перехода в его начальное состояние.2.Для всех состояний q из Q, входов a из Σ или a = ε и магазинных символов Y из ΓδN(q, a, Y) содержит все пары из δF(q, a, Y), т.е. PN имитирует PF.3.Для всех допускающих состояний q из F и магазинных символов Y из Γ U {X0}δN(q, ε, Y) содержит (p, ε). По этому правилу, как только PF допускает, PN может начать опустошение магазина без чтения входных символов.4.Для всех магазинных символов Y из Γ U {X0}, δN(p, ε, Y) = {(p, ε)}.
Попав в состояниеp (только в случае, когда PF допускает), PN выталкивает символы из магазина до егоопустошения. Входные символы при этом не читаются.Теперь нужно доказать, что w ∈ N(PN) тогда и только тогда, когда w ∈ L(PF). Идеианалогичны теореме 6.9. Достаточность представляет собой непосредственную имитацию, а необходимость требует проверки ограниченного числа действий, которые можетсовершить МП-автомат PN.248Стр. 248ÃËÀÂÀ 6.
ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞ*(Достаточность) Пусть (q0, w, Z0) |− (q, ε, α) для некоторого допускающего состоянияPFq и цепочки α в магазине. Вспомним, что каждый переход PF есть и у PN, и что теорема 6.5*разрешает нам держать X0 в магазине под символами из Γ. Тогда (q0, w, Z0X0) |− (q, ε, αX0).PNСледовательно, PN может совершить следующие действия.**PNPN(p0, w, X0) |− (q0, w, Z0X0) |− (q, ε, αX0) |− (p, ε, ε)PNПервый переход соответствует правилу 1 построения PN, а последняя последовательность переходов — правилам 3 и 4.
Таким образом, PN допускает w по пустому магазину.(Необходимость) Единственный путь, по которому PN может опустошить свой магазин, состоит в достижении состояния p, так как X0 находится в магазине и являетсясимволом, для которого у PF переходы не определены. PN может достичь состояния pтолько тогда, когда PF приходит в допускающее состояние. Первым переходом автомата PN может быть только переход, заданный правилом 1. Таким образом, каждое допускающее вычисление PN выглядит следующим образом (q — допускающее состояние автомата PF).**PNPN(p0, w, X0) |− (q0, w, Z0X0) |− (q, ε, αX0) |− (p, ε, ε)PNКроме того, между МО (q0, w, Z0X0) и (q, ε, αX0) все переходы являются переходамиавтомата PF. В частности, X0 никогда не появляется на вершине магазина до достиженияМО (q, ε, αX0).4 Таким образом, приходим к выводу, что у PF есть такое же вычисление,*но без X0 в магазине, т.е.
(q0, w, Z0) |− (q, ε, α). Итак, PF допускает w по заключительномуPFсостоянию, т.е. w ∈ L(PF). 6.2.5. Óïðàæíåíèÿ ê ðàçäåëó 6.26.2.1.Постройте МП-автоматы, допускающие следующие языки. Можно использоватьдопускание как по заключительному состоянию, так и по пустому магазину —что удобнее:а) (∗) {0n1n | n ≥ 1};б) множество всех цепочек из 0 и 1, в префиксах которых количество символов1 не больше количества символов 0;в) множество всех цепочек из 0 и 1 с одинаковыми количествами символов 0 и 1.4Хотя α может быть ε, и в этом случае PF опустошает свой магазин и одновременно допус-кает.6.2. ßÇÛÊÈ ÌÏ-ÀÂÒÎÌÀÒÎÂСтр. 2492496.2.2.(!) Постройте МП-автоматы, допускающие следующие языки:а) (∗) {aibjck | i = j или j = k}.
Заметим, что этот язык отличается от языка из упражнения 5.1.1, б;б) множество всех цепочек из 0 и 1, у которых количество символов 0 вдвоебольше количества символов 1.6.2.3.(!!) Постройте МП-автоматы, допускающие следующие языки:а) {aibjck | i ≠ j или j ≠ k};б) множество всех цепочек из символов a и b, которые не имеют вида ww, т.е.не являются повторениями никакой цепочки.6.2.4.Пусть P — МП-автомат, допускающий по пустому магазину язык L = N(P), ипусть ε ∉ L. Опишите, как изменить P, чтобы он допускал L U {ε} по пустомумагазину.6.2.5.МП-автомат P = ({q0, q1, q2, q3, f}, {a, b}, {Z0, A, B}, δ, q0, Z0, {f}) имеет следующее определение δ.δ(q0, a, Z0) = (q1, AAZ0)δ(q0, b, Z0) = (q2, BZ0)δ(q0, ε, Z0) = (f, ε)δ(q1, a, A) = (q1, AAA)δ(q1, b, A) = (q1, ε)δ(q1, ε, Z0) = (q0, Z0)δ(q2, a, B) = (q3, ε)δ(q2, b, B) = (q2, BB)δ(q2, ε, Z0) = (q0, Z0)δ(q3, ε, B) = (q2, ε)δ(q3, ε, Z0) = (q1, AZ0)Фигурные скобки опущены, поскольку каждое из указанных множеств имееттолько один выбор перехода.а) (∗) приведите трассу выполнения (последовательность МО), по которой видно, что bab ∈ L(P);б) приведите трассу выполнения, показывающую, что abb ∈ L(P);в) укажите содержимое магазина после того, как P прочитал b7a4 на входе;г) (!) дайте неформальное описание L(P).6.2.6.Рассмотрим МП-автомат P из упражнения 6.1.1:а) преобразуйте P в другой МП-автомат P1, допускающий по пустому магазинутот же язык, который допускается P по заключительному состоянию, т.е.N(P1) = L(P);б) постройте МП-автомат P2 такой, что L(P2) = N(P), т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
