dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 59

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 59)

Вэтом разделе определяются детерминированные МП-автоматы и частично исследуютсяработы, которые им под силу и на которые они не способны.6.4.1. Îïðåäåëåíèå äåòåðìèíèðîâàííîãî ÌÏ-àâòîìàòàИнтуитивно МП-автомат является детерминированным, если в любой ситуации у негонет возможности выборов перехода. Эти выборы имеют два вида. Если δ(q, a, X) содержит более одной пары, то МП-автомат безусловно не является детерминированным, поскольку можно выбирать из этих двух пар. Однако если δ(q, a, X) всегда одноэлементно,все равно остается возможность выбора между чтением входного символа и совершением ε-перехода.

Таким образом, МП-автомат P = (Q, Σ, Γ, δ, q0, Z0, F) определяется какдетерминированный (ДМП-автомат), если выполнены следующие условия.1.δ(q, a, X) имеет не более одного элемента для каждого q из Q, a из Σ или a = ε и X из Γ.2.Если δ(q, a, X) непусто для некоторого a из Σ, то δ(q, ε, X) должно быть пустым.Пример 6.16. Оказывается, КС-язык Lwwr из примера 6.2 не имеет ДМП-автомата.Однако путем помещения “центрального маркера” c в середину слов получается языкLwcwr = {wcwR | w ∈ (0 + 1)*}, распознаваемый некоторым ДМП-автоматом.Стратегией этого ДМП-автомата является заталкивание символов 0 и 1 в магазин допоявления на входе маркера c.

Затем автомат переходит в другое состояние, в которомсравнивает входные и магазинные символы и выталкивает магазинные в случае их сов260Стр. 260ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞпадения. Находя несовпадение, он останавливается без допускания (“умирает”); его входне может иметь вид wcwR. Если путем удаления магазинных символов он достигает стартового символа, отмечающего дно магазина, то он допускает свой вход.По своей идее этот автомат очень похож на МП-автомат, изображенный на рис. 6.2.Однако тот МП-автомат был недетерминированным, поскольку в состоянии q0 всегдаимел возможность выбора между заталкиванием очередного входного символа в магазини переходом в состояние q1 без чтения входа, т.е. он должен был угадывать, достигнутали середина.

ДМП-автомат для Lwcwr изображен в виде диаграммы переходов нарис. 6.11.εεНачало,,,ε,Рис. 6.11. ДМП-автомат, допускающий LwcwrОчевидно, этот МП-автомат детерминирован. У него никогда нет выбора перехода водном и том же состоянии и при использовании одних и тех же входных и магазинныхсимволов. Что же касается выбора между использованием входного символа или ε, тоединственным ε-переходом, который он совершает, является переход из q1 в q2 с Z0 навершине магазина.

Однако в состоянии q1 с Z0 на вершине других переходов нет. †6.4.2. Ðåãóëÿðíûå ÿçûêè è äåòåðìèíèðîâàííûå ÌÏ-àâòîìàòûДМП-автоматы допускают класс языков, который находится между регулярными и КСязыками. Вначале докажем, что языки ДМП-автоматов включают в себя все регулярные.Теорема 6.17. Если L — регулярный язык, то L = L(P) для некоторого ДМП-автомата P.Доказательство. По существу, ДМП-автомат может имитировать детерминированный конечный автомат.

МП-автомат содержит некоторый символ Z0 в магазине, так какон должен иметь магазин, но в действительности он игнорирует магазин, используятолько состояние. Формально, пусть A = (Q, Σ, δA, q0, F) — конечный автомат. ПостроимP = (Q, Σ, {Z0}, δP, q0, Z0, F), определив δP(q, a, Z0) = {(p, Z0)} для всех состояний p и q изQ, при которых δA(q, a) = p.*∧Мы утверждаем, что (q0, w, Z0) |− (p, ε, Z0) тогда и только тогда, когда δ (q0, w) = p,Pт.е.

P имитирует A, используя его состояние. Доказательства в обе стороны просты и6.4. ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞСтр. 261261проводятся индукцией по |w|, поэтому оставляются для завершения читателю. Посколькукак A, так и P допускают, достигнув какого-либо состояния из F, приходим к выводу, чтоих языки равны. †Если мы хотим, чтобы ДМП-автомат допускал по пустому магазину, то обнаруживаем, что возможности по распознаванию языков существенно ограничены.

Говорят, чтоязык L имеет префиксное свойство, или свойство префиксности, если в L нет двух различных цепочек x и y, где x является префиксом y.Пример 6.18. Язык Lwcwr из примера 6.16 имеет префиксное свойство, т.е. в нем неможет быть двух разных цепочек wcwR и xcxR, одна из которых является префиксом другой. Чтобы убедиться в этом, предположим, что wcwR — префикс xcxR, и w ≠ x. Тогда wдолжна быть короче, чем x. Следовательно, c в w приходится на позицию, в которой xимеет 0 или 1, а это противоречит предположению, что wcwR — префикс xcxR.С другой стороны, есть очень простые языки, не имеющие префиксного свойства.Рассмотрим {0}*, т.е.

множество всех цепочек из символов 0. Очевидно, в этом языкеесть пары цепочек, одна из которых является префиксом другой, так что этот язык не обладает префиксным свойством. В действительности, из любых двух цепочек одна является префиксом другой, хотя это условие и сильнее, чем то, которое нужно для отрицанияпрефиксного свойства.

†Заметим, что язык {0}* регулярен. Таким образом, неверно, что каждый регулярныйязык есть N(P) для некоторого ДМП-автомата P. Оставляем в качестве упражнения следующее утверждение.Теорема 6.19. Язык L есть N(P) для некоторого ДМП-автомата P тогда и только тогда,когда L имеет префиксное свойство и L есть L(P′) для некоторого ДМП-автомата P′. †6.4.3. Äåòåðìèíèðîâàííûå ÌÏ-àâòîìàòû è ÊÑ-ÿçûêèМы уже видели, что ДМП-автоматы могут допускать языки вроде Lwcwr, которые неявляются регулярными. Для того чтобы убедиться в его нерегулярности, предположим,что это не так, и используем лемму о накачке. Пусть n — константа из леммы. Рассмотрим цепочку w = 0nc0n из Lwcwr.

Если ее “накачивать”, изменяется длина первой группысимволов 0, и получаются цепочки из Lwcwr, у которых “центральный маркер” расположен не в центре. Так как эти цепочки не принадлежат Lwcwr, получаем противоречие и делаем вывод, что Lwcwr нерегулярен.С другой стороны, существуют КС-языки, вроде Lwwr, которые не могут допускатьсяпо заключительному состоянию никаким ДМП-автоматом. Формальное доказательствовесьма сложно, но интуитивно прозрачно. Если P — ДМП-автомат, допускающий Lwwr,то при чтении последовательности символов 0 он должен записать их в магазин или сделать что-нибудь равносильное для подсчета их количества. Например, записывать один Xдля каждых 00 на входе и использовать состояние для запоминания четности или нечетности числа символов 0.262Стр.

262ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞПредположим, P прочитал n символов 0 и затем видит на входе 110n. Он должен проверить, что после 11 находятся n символов 0, и для этого он должен опустошить свой магазин.5 Теперь он прочитал 0n110n. Если далее он видит идентичную цепочку, он должен допускать, поскольку весь вход имеет вид wwR, где w = 0n110n.

Однако если P видит 0m110m,где m ≠ n, он должен не допускать. Поскольку его магазин пуст, он не может запомнить,каким было произвольное целое n, и не способен допустить Lwwr. Подведем итог.• Языки, допускаемые ДМП-автоматами по заключительному состоянию, включают регулярные языки как собственное подмножество, но сами образуют собственное подмножество КС-языков.6.4.4.

Äåòåðìèíèðîâàííûå ÌÏ-àâòîìàòû è íåîäíîçíà÷íûåãðàììàòèêèМощность ДМП-автоматов можно уточнить, заметив, что все языки, допускаемыеими, имеют однозначные грамматики. К сожалению, класс языков ДМП-автоматов несовпадает с подмножеством КС-языков, не являющихся существенно неоднозначными.Например, Lwwr имеет однозначную грамматику S → 0S0 | 1S1 | ε, хотя и не являетсяДМП-автоматным языком. Следующая теорема уточняет заключительное утверждениеиз подраздела 6.4.3.Теорема 6.20.

Если L = N(P) для некоторого ДМП-автомата P, то L имеет однозначную КС-грамматику.Доказательство. Утверждаем, что конструкция теоремы 6.14 порождает однозначную КС-грамматику G, когда МП-автомат, к которому она применяется, детерминирован. Вначале вспомним (см. теорему 5.29), что для однозначности грамматики G достаточно показать, что она имеет уникальные левые порождения.Предположим, P допускает w по пустому магазину. Тогда он делает это с помощьюодной-единственной последовательности переходов, поскольку он детерминирован и неможет работать после опустошения магазина. Зная эту последовательность переходов,мы можем однозначно определить выбор каждой продукции в левом порождении w в G.Правило автомата P, на основании которого применяется продукция, всегда одно.

Ноправило, скажем, δ(q, a, X) = {(r, Y1Y2…Yk)}, может порождать много продукций грамматики G, с различными состояниями в позициях, отражающих состояния P после удалениякаждого из Y1, Y2, …, Yk. Однако, поскольку P детерминирован, осуществляется толькоодна из этих последовательностей переходов, поэтому только одна из этих продукций вдействительности ведет к порождению w. †Мы можем, однако, доказать больше: даже языки, допускаемые ДМП-автоматами позаключительному состоянию, имеют однозначные грамматики. Поскольку мы знаем5Это интуитивное утверждение требует сложного формального доказательства; возможен лидругой способ для P сравнить два равных блока символов 0?6.4. ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞСтр. 263263лишь, как строятся грамматики, исходя из МП-автоматов, допускающих по пустому магазину, нам придется изменять язык, чтобы он обладал префиксным свойством, а затеммодифицировать грамматику, чтобы она порождала исходный язык.

Обеспечим это спомощью “концевого маркера”.Теорема 6.21. Если L = L(P) для некоторого ДМП-автомата P, то L имеет однозначную КС-грамматику.Доказательство. Пусть $ будет “концевым маркером”, отсутствующим в цепочкахязыка L, и пусть L′ = L$. Таким образом, цепочки языка L′ представляют собой цепочкииз L, к которым дописан символ $. Тогда L′ имеет префиксное свойство, и по теореме 6.19 L′ = N(P′) для некоторого ДМП-автомата P′.6 По теореме 6.20 существует однозначная грамматика G′, порождающая язык N(P′), т.е. L′.Теперь по грамматике G′ построим G, для которой L(G) = L. Для этого нужно лишьизбавиться от маркера $ в цепочках. Будем рассматривать $ как переменную грамматикиG и введем продукцию $ → ε; остальные продукции G и G′ одинаковы.

ПосколькуL(G′) = L′, получаем, что L(G) = L.Утверждаем, что G однозначна. Действительно, левые порождения в G совпадают слевыми порождениями в G′, за исключением последнего шага в G — изменения $ на ε.Таким образом, если бы терминальная цепочка w имела два левых порождения в G, тоw$ имела бы два порождения в G′. Поскольку G′ однозначна, G также однозначна. †6.4.5. Óïðàæíåíèÿ ê ðàçäåëó 6.46.4.1.Для каждого из следующих МП-автоматов укажите, является ли он детерминированным.

Характеристики

Список файлов книги