dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 58
Текст из файла (страница 58)
6.10 показано, как последовательность символов Y1, Y2, …, Yk удаляется измагазина. До удаления Y1 прочитывается вход x1. Подчеркнем, что это “удаление” является окончательным результатом, возможно, многих переходов. Например, первый переход может изменить Y1 на некоторый другой символ Z, следующий — изменить Z на UV,дальнейшие переходы — вытолкнуть U, а затем V. Окончательный результат заключается в том, что Y1 изменен на ничто, т.е. вытолкнут, и все прочитанные к этому моментувходные символы образуют x1.На рис.
6.10 показано также окончательное изменение состояния. Предполагается,что МП-автомат начинает работу в состоянии p0 с Y1 на вершине магазина. После всехпереходов, результат которых состоит в удалении Y1, МП-автомат находится в состоянииp1. Затем он достигает окончательного удаления Y2, прочитывая при этом x2 и приходя,возможно, за много переходов, в состояние p2.
Вычисление продолжается до тех пор, пока каждый из магазинных символов не будет удален.6.3. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ ÌÏ-ÀÂÒÎÌÀÒÎÂ È ÊÑ-ÃÐÀÌÌÀÒÈÊСтр. 255255Наша конструкция эквивалентной грамматики использует переменные, каждая из которых представляет “событие”, состоящее в следующем.1.Окончательное удаление некоторого символа X из магазина.2.Изменение состояния от некоторого p (вначале) до q, когда X окончательно заменяется ε в магазине.Такую переменную обозначим составным символом [pXq]. Заметим, что эта последовательность букв является описанием одной переменной, а не пятью символами грамматики. Формальное построение дается следующей теоремой.Теорема 6.14.
Пусть P = (Q, Σ, Γ, δ, q0, Z0) — МП-автомат. Тогда существует КСграмматика G, для которой L(G) = N(P).Доказательство. Построим G = (V, Σ, R, S), где V состоит из следующих переменных.1.Специальный стартовый символ S.2.Все символы вида [pXq], где p и q — состояния из Q, а X — магазинный символ из Γ.Грамматика G имеет следующие продукции:а) продукции S → [q0Z0p] для всех состояний p. Интуитивно символ вида[q0Z0p] предназначен для порождения всех тех цепочек w, которые приводятP к выталкиванию Z0 из магазина в процессе перехода из состояния q0 в со*стояние p. Таким образом, (q, w, Z0) |− (q, ε, ε). Эти продукции гласят, чтостартовый символ S порождает все цепочки w, приводящие P к опустошениюмагазина после старта в начальной конфигурации;б) пусть δ(q, a, X) содержит пару (r, Y1Y2…Yk), где a есть либо символ из Σ, либоε, а k — некоторое неотрицательное число; при k = 0 пара имеет вид (r, ε).Тогда для всех списков состояний r1, r2, …, rk в грамматике G есть продукция[qXrk] → a[rY1r1][r1Y2r2]…[rk–1Ykrk].Она гласит, что один из путей выталкивания X и перехода из состояния q всостояние rk заключается в том, чтобы прочитать a (оно может быть равно ε),затем использовать некоторый вход для выталкивания Y1 из магазина с переходом из состояния r в состояние r1, далее прочитать некоторый вход, вытолкнуть Y2 и перейти из r1 в r2, и т.д.Докажем корректность неформальной интерпретации переменных вида [qXp]:**• [qXp] ⇒ w тогда и только тогда, когда (q, w, X) |− (p, ε, ε).**(Достаточность) Пусть (q, w, X) |− (p, ε, ε).
Докажем, что [qXp] ⇒ w, используя инPдукцию по числу переходов МП-автомата.256Стр. 256ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞБазис. Один шаг. Пара (p, ε) должна быть в δ(q, w, X), и w есть либо одиночныйсимвол, либо ε. Из построения G следует, что [qXp] → w является продукцией, поэтому [qXp] ⇒ w.*Индукция. Предположим, что последовательность (q, w, X) |− (p, ε, ε) состоит из nпереходов, и n > 1. Первый переход должен иметь вид*(q, w, X) |− (r0, X, Y1Y2…Yk) |− (p, ε, ε),где w = aX для некоторого a, которое является либо символом из Σ, либо ε.
Отсюда следует, что пара (r0, Y1Y2…Yk) должна быть в δ(q, a, X). Кроме того, по построению G существует продукция [qXrk] → a[r0Y1r1][r1Y2r2]…[rk–1Ykrk], у которой rk = p и r1, r2, …, rk–1 — некоторые состояния из Q.На рис. 6.10 показано, что символы Y1, Y2, …, Yk удаляются из магазина по очереди, идля i = 1, 2, …, k – 1 можно выбрать состояние pi, в котором находится МП-автомат приудалении Yi.
Пусть X = w1w2…wk, где wi — входная цепочка, которая прочитывается до*удаления Yi из магазина. Тогда (ri–1, wi, Yi) |− (ri, ε, ε).Поскольку ни одна из указанных последовательностей переходов не содержит более,чем n переходов, к ним можно применить предположение индукции. Приходим к выво*ду, что [ri–1Yiri] ⇒ wi. Соберем эти порождения вместе.*[qXrk] ⇒ a[r0Y1r1][r1Y2r2]…[rk–1Ykrk] ⇒*aw1[r1Y2r2]…[rk–1Ykrk] ⇒*aw1w2[r2Y3r3]…[rk–1Ykrk] ⇒…aw1w2…wk = wЗдесь rk = p.(Необходимость) Доказательство проводится индукцией по числу шагов в порождении.Базис. Один шаг.
Тогда [qXp] → w должно быть продукцией. Единственная возможность для существования этой продукции — если в P есть переход, в котором X выталкивается, а состояние q меняется на p. Таким образом, пара (p, ε) должна быть вδ(q, a, X), и a = w. Но тогда (q, w, X) |− (p, ε, ε).*Индукция. Предположим, что [qXp] ⇒ w за n шагов, где n > 1. Рассмотрим подробно первую выводимую цепочку, которая должна выглядеть следующим образом.*[qXrk] ⇒ a[r0Y1r1][r1Y2r2]…[rk–1Ykrk] ⇒ wЗдесь rk = p.
Эта продукция должна быть в грамматике, так как (r0, Y1Y2…Yk) есть вδ(q, a, X).6.3. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ ÌÏ-ÀÂÒÎÌÀÒÎÂ È ÊÑ-ÃÐÀÌÌÀÒÈÊСтр. 257257*Цепочку w можно разбить на w = aw1w2…wk так, что [ri–1Yiri] ⇒ wi для всех i = 1, 2, …,k – 1. По предположению индукции для всех этих i верно следующее утверждение.*(ri–1, wi, Yi) |− (ri, ε, ε)Используя теорему 6.5 для того, чтобы поместить нужные цепочки вокруг wi на входе ипод Yi в магазине, получим*(ri–1, wiwi+1…wk, YiYi+1…Yk) |− (ri, wi+1…wk, Yi+1…Yk).Соберем все эти последовательности вместе и получим следующее порождение.(q, aw1w2…wk, X)|−*(r0, w1w2…wk, Y1Y2…Yk) |−***(r1, w2w3…wk, Y2Y3…Yk) |− (r2, w3…wk, Y3…Yk) |− … |− (rk, ε, ε)*Поскольку rk = p, мы доказали, что (q, w, X) |− (p, ε, ε).**Завершим доказательство.
S ⇒ w тогда и только тогда, когда [q0Zp0] ⇒ w для некоторого p в соответствии с построенными правилами для стартового символа S. Выше уже**доказано, что [q0Zp0] ⇒ w тогда и только тогда, когда (q, w, Z0) |− (p, ε, ε), т.е. когда Pдопускает w по пустому магазину. Таким образом, L(G) = N(P).
Пример 6.15. Преобразуем в грамматику МП-автомат PN = ({q}, {i, e}, {Z}, δN, q, Z)из примера 6.10. Напомним, что PN допускает все цепочки, которые нарушают правило,что каждое e (else) должно соответствовать некоторому предшествующему i (if). Так какPN имеет только одно состояние и один магазинный символ, грамматика строится просто. В ней есть лишь следующие две переменные:а) S — стартовый символ, который есть в каждой грамматике, построенной методом теоремы 6.14;б) [qZq] — единственная тройка, которую можно собрать из состояний и магазинных символов автомата PN.Грамматика G имеет следующие продукции.1.Единственной продукцией для S является S → [qZq].
Но если бы у МП-автомата было n состояний, то было бы и n продукций такого вида, поскольку последним можетбыть любое из n состояний. Первое состояние должно быть начальным, а магазинный символ — стартовым, как в нашей продукции выше.2.Из того факта, что δN(q, i, Z) содержит (q, ZZ), получаем продукцию[qZq] → i[qZq][qZq]. В этом простом примере есть только одна такая продукция.
Ноесли бы у автомата было n состояний, то одно такое правило порождало бы n2 продукций, поскольку как промежуточным состоянием в теле, так и последним состоянием в голове и теле могли быть любые два состояния. Таким образом, если бы r и p258Стр. 258ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞбыли двумя произвольными[qZp] → i[qZr][rZp].3.состояниями,тосоздаваласьбыпродукцияИз того, что δN(q, e, Z) содержит (q, ε), получаем продукцию [qZq] → e. Заметим, что вэтом случае список магазинных символов, которыми заменяется Z, пуст, поэтому единственным символом в теле является входной символ, приводящий к этому переходу.Можно для удобства заменить тройку [qZq] каким-либо простым символом,например A.
В таком случае грамматика состоит из следующих продукций.S→AA → iAA | eВ действительности можно заметить, что S и A порождают одни и те же цепочки, поэтому их можно обозначить одинаково и записать грамматику в окончательном виде.G = ({S}, {i, e}, {S → iSS | e}, S)6.3.3. Óïðàæíåíèÿ ê ðàçäåëó 6.36.3.1.(∗) Преобразуйте грамматикуS → 0S1 | AA → 1A0 | S | εв МП-автомат, допускающий тот же язык по пустому магазину.6.3.2.Преобразуйте грамматикуS → aAAA → aS | bS | aв МП-автомат, допускающий тот же язык по пустому магазину.6.3.3.(∗) Преобразуйте МП-автомат P = ({p, q}, {0, 1}, {X, Z0}, δ, q, Z0) в КС-грамматику, где δ задана следующим образом.1.δ(q, 1, Z0) = {(q, XZ0)}.2.δ(q, 1, X) = {(q, XX)}.3.δ(q, 0, X) = {(p, X)}.4.δ(q, ε, X) = {(q, ε)}.5.δ(p, 1, X) = {(p, ε)}.6.δ(p, 0, Z0) = {(q, Z0)}.6.3.4.Преобразуйте МП-автомат из упражнения 6.1.1 в КС-грамматику.6.3.5.Ниже приведены КС-языки. Постройте для каждого из них МП-автомат, допускающий этот язык по пустому магазину.
При желании можно сначала построитьКС-грамматику для этого языка, а затем преобразовать ее в МП-автомат.6.3. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ ÌÏ-ÀÂÒÎÌÀÒÎÂ È ÊÑ-ÃÐÀÌÌÀÒÈÊСтр. 259259а) {anbmc2(n+m) | n ≥ 0, m ≥ 0};б) {aibjck | i = 2j или j = 2k};в) {0n1m | n ≤ m ≤ 2n}.6.3.6.(∗!) Докажите, что если P — МП-автомат, то существует МП-автомат P1 с одним состоянием, для которого N(P1) = N(P).6.3.7.(!) Пусть у нас есть МП-автомат с s состояниями, t магазинными символами, вправилах которого длина цепочки, замещающей символ в магазине, не превышает u. Дайте как можно более точную верхнюю оценку числа переменныхКС-грамматики, которая строится по этому МП-автомату с помощью методаиз раздела 6.3.2.6.4. Äåòåðìèíèðîâàííûå àâòîìàòû ñ ìàãàçèííîéïàìÿòüþХотя МП-автоматы по определению недетерминированы, их детерминированныйслучай чрезвычайно важен. В частности, синтаксические анализаторы в целом ведут себякак детерминированные МП-автоматы, поэтому класс языков, допускаемых этими автоматами, углубляет понимание конструкций, пригодных для языков программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
