Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 59
Текст из файла (страница 59)
АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 268 были двуми произвольными состояниями, то создавалась бы продукция [д٠— > 1[ уЬ.] [ггР]. 3. Из того, что бь(д, е, к) содержит (у, в), получаем пролукпию [дед] -+ е. Заметим, что в эюм случае список магазинных символов, которыми заменяется х, пуст, поэтому единственным символом в теле является входной символ, приводящий к этому переходу. Можно лля удобства заменить тройку [ уЩ каким-либо простым символом, например А. В таком случае грамматика состоит из следующих продукций. Я вЂ” >А А — >!АА ~ е В действительности можно заметить, что Я и А порождают одни и те же цепочки, поэтому нх можно обозначизь одинаково и записать грамматику в окончательном виде. О = ((5], (О е), (Я -+ 155 ] е], Ь) 6.3.3. Чпразкнения к разделу б.3 6.3.1. (е) Преобразуйте грамматику 5 — ь 051]А А †>1АО]Я)е в МП-автомат, допускающий тот же язык по пустому магазину.
6.3.2. Преобразуйте грамматику 5 — з аАА А -э аЬ' ! ЬЯ ~ а в МП-автомат, допускающий тот же язык по пустому магазину. 6.3.3. (ь) Преобразуйте МП-автомат Р = ((р, о], (О, 1], (Х, У,], 4 ц, Хе) в КС-грамматику, гле Б задана слелующим образом. 1, аксу, 1, Уа) = ((о, ХХе) ].
г, Ж,2, 1, х) = нп, хх)]. дд,о,х) = [(Р,х)]. 4. о(у, е, Х) = ((гу, еН. 5. о(Р, 1, Х) = ((Р, к) ]. б, Др, О, Х,) = Кд, Хя)]. 6.3.4. Преобразуйте МП-автомат из упражнения 6.1.1 в КС-грамматику. 6.3.5. Ниже приведены КС-языкн. Постройте лля каждого из них МП-автомат, лопускающий этот язык по пустому магазину. При желании можно сначала построить КС-грамматику лля этого языка, а затем преобразовать ее в МП-автомат. 6.3. ЭКВИВАЛЕНТНОСТЬ МП-АВТОМАТОВ И КС-ГРАММАТИК 259 а) (аЬ с~~~ ~/ц~о,в>0); б) (а'Ь'с" ) 1=2уили)= 2к); в) (О"1'" ! и <и <2н).
6.3.6. (в!) Докажите, что если Р— МП-автомат, то существует МП-автомат Р, с одним состоянием, для которого '~(Р,) = Ф(Р). 6.3.7. (1) Пусть у нас есть МП-автомат с з состояниями, г магазинными символами, в правилах которого длина цепочки, замещающей символ в магазине, не превышает и. Дайте как можно более точную верхнюю оценку числа переменных КС-грамматики, которая строится по этому МП-автомату с помощью метода из раздела 6.3,2. 6.4. Детерминированные автоматы с магазинной памятью Хотя МП-автоматы по определению недетерминированы, их детерминированный случай чрезвычайно важен. В частности, синтаксические анализаторы в целом ведут себя как летерминированные МП-автоматы, поэтому класс языков, допускаемых этими автоматами, углубляет понимание конструкций, пригодных для языков программирования.
В этом разделе определяются детерминированные МП-автоматы и частично исследуются работы, которые им под силу и на которые они не способны. 6.4.1. Определение детерминированного МП-автомата Интуитивно МП-автомат является детерминированным, если в любой ситуации у него нет возможности выборов перехода. Эти выборы имеют два вида. Если ~д, а, Х) содержит более одной пары, то МП-автомат безусловно не является детерминированным, поскольку можно выбирать из этих лвух пар. Однако если фд, а, Х) всегда одноэлементно, все равно остается возможность выбора между чтением входного символа и совершением е-перехода. Таким образом, МП-автомат Р= © Х, Г, 6,0,,2„, Р) определяется как детерминированный (ДМП-автомат), если выполнены следующие условия. 1.
б(о, а, Х) имеет не более одного элементадля каждого азиз Я а изт или а= е иХиз Г. 2. Если б(гу, а, Х) непусто для некоторого а из Х„то 4д, е, Х) должно быть пустым. Пример 6.16. Оказывается, КС-язык Е„„,„из примера 6.2 не имеет ДМП-автомата. Однако путем помещения "центрального маркера" с в середину слов получается язык 1„,,„,, = (иси к ~ и е (О ь 1) ), распознаваемый некоторым ДМП-автоматом. Стратегией этого ДМП-автомата является заталкивание символов 0 и 1 в магазин до появления на входе маркера с. Затем автомат переходит в другое состояние, в котором сравнивает входные и магазинные символы и выталкивает магазинные в случае их сов- ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 260 алдения. Находя несовпадение, он останавливается без допускания (" умирает*'); его вход не может иметь вид !ссчс .
Если путем удаления магазинных символов он достигает стартового символа, отмечающего дно магазина, то он допускает свой вход. Па своей идее этот автомат очень похож на МП-автомат, изображенный на рис. 6.2. Однако тот МП-автомат был недетерминированным, поскольку в состоянии до всегда янез возможность выбора между заталкиванием очередного входного символа в магазин и переходом в состояние д, без чтения входа, т.е. он должен был угадывать, достигнута ля середина.
ДМП-автомат для ! „„, изображен в виде диаграммы переходов на рнс. 6.11. а,х,/аг, !,г,/!г, а,а/аа а,!/а! !,а/!а 1,!/1! а,а/в /,!/с с, а/а с, 1/! Рис. 6. П. Дй//7-автомапи допускающий 1 Очевидно, этот МП-автомат детерминирован. У него никогда нет выбора перехода в одном и том же состоянии и при использовании одних и тех же входных и магазинных символов. Что же касается выбора между использованием входного символа или я, то единственным в-переходом, который он совершает, является переход из д/ в д/ с Уо/ на вершине магазина.
Однако в состоянии д, с Ес на вершине других переходов нет. Е) би, ДЕТЕРМИНИРОВАННЫЕ АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 261 6.4.2. Регулярные языки и детерминированные МП-автоматы ДМП-автоматы допускают класс языков, который находится между регулярными и КС- языками. Вначале докажем, что языки ДМП-автоматов включают в себя все регулярные. Теорема 6.17. Если 1. — регулярный язык, то Л = ЦР) для некоторого ДМП-автомата Р. Доказательство. По существу, ДМП-автомат может имитировать детерминированный конечный автомат.
МП-автомат содержит некоторый символ са в магазине, так как ак должен иметь магазин, но в действительности он игнорирует магазин, используя только состояние. Формально, пусть А = Я, Х, бт д,, Р) — конечный автомат. Построим Р = (Д Х, (Лс), б/ч д,, а/„Р), определив б/(д, и, ас) = ((Р, сю) ) для всех состояний р и д из й, при которых 4,(д, а) = Р. Мы утверждаем, что (д,, и, ас) (- (Р, а сп/) тогда и только тогда, когда Б (д,, !и) = р, /' т.е. Р имитирует А, используя его состояние.
Доказательства в обе стороны просты и проводятся индукцией по )и), поэтому оставляются для завершения читателю. Поскольку как А, так и Р допускают, достигнув какого-либо состояния из Р, прихолим к выводу, что их языки равны. П Если мы хотим, чтобы ДМП-автомат допускал по пустому магазину, то обнаруживаем, что возможности по распознаванию языков сушественно ограничены. Говорят„что язык 1. имеет префикспое свойство, или свойство префикспости, если в 1. нет двух различных цепочек х ну, где х является префиксом у. Пример 6Л8. Язык 1„„„,, из примера 6.16 имеет префиксное свойство, т.е.
в нем не может быть двух разных цепочек згсзг~ и хсхк, одна из которых является префиксом другой. Чтобы убедиться в этом, предположим, что и си — префикс хсх, и и е х. Тогда и к к должна быть короче, чем х. Следовательно, с в и приходится на позицию, в которой х имеет 0 или 1, а это противоречит предположению, что исв — префикс хсх . к к С другой стороны, есть очень простые языки, не имеющие префиксного свойства. Рассмотрим (0), т.е. множество всех цепочек из символов О. Очевидно, в этом языке есть пары цепочек, одна из которых является префиксом другой, так что этот язык не обладает префиксным свойством. В действительности, из любых двух цепочек одна является префиксом другой, хотя это условие и сильнее, чем то, которое нужно для отрицания префиксного свойства. Е) Заметим, что язык (0) регулярен.
Таким образом, неверно, что каждый регулярный язык есть И(Р) для некоторого ДМП-автомата Р. Оставляем в качестве упражнения следуюшее утверждение. Теорема 6.19. Язык с есть Х(Р) для некоторого ДМП-автомата Р тогда и только тогда, когда Т, имеет префиксное свойство и ь' есть б(Р "1 для некоторого ДМП-автомата Р'. ЕЗ 6.4.3, Детерминированные МП-автоматы и КС-языки Мы уже видели, что ДМП-автоматы могут допускать языки вроде (.„„„которые не являются регулярными. Для того чтобы убедиться в его нерегулярности, предположим„ что это не так, и используем лемму о накачке. Пусть п — константа из леммы.
Рассмотрим цепочку и = 0"сО" из (,кпп Если ее "накачивать", изменяется длина первой группы символов О, и получаются цепочки из (.,ппп у которых "центральный маркер" расположен не в центре. Так как эти цепочки не принадлежат Е„,пп получаем противоречие и делаем вывод, что Е„„„нерегулярен. С другой стороны, существуют КС-языки, вроде Т,„„„, которые не могут допускаться по заключительному состоянию никаким ДМП-автоматом. Формальное доказательство весьма сложно, но интуитивно прозрачно. Если Р— ДМП-автомат, допускаюший г'„.„ то при чтении последовательности символов 0 он должен записать их в магазин или сделать что-нибудь равносильное для подсчета их количества. Например, записывать одинХ для каждых 00 на входе и использовать состояние для запоминания четности или нечет- ности числа символов О. ГЛАВА б. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 262 Предположим, Р прочи~ал и символов 0 и затем видит нв входе 110".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
