Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 57
Текст из файла (страница 57)
Вспомним, что каждый переход Рг есть и у Р,, и что теорема 6.5 разрешает нам держать Х, в магазине под символами из Г. Тогда (гус, н, хвХс) )- (д, е, аХс). л Следовательно, Рн может совершить следующие действия. (ро, зг,Хо) )- (Чо н', ХоХо) !- (Ч, е, аХе) !- (р, е, е) Первый переход соответствует правилу! построения Рм а последняя последовательность переходов — правилам 3 и 4.
Таким образом, Рн допускае~ н по пустому магазину. (Необходимость) Единственный путь, по которому Рн может опустошить свой магазин, состоит в достижении состояния р, так как Хе находится в магазине и является символом, для которого у Рг переходы не определены. Рм может достичь состояния р только тогда, когда Рк приходит в допускающее состояние. Первым переходом автомата Рн может быть только переход, заданный правилом 1. Таким образом, каждое допускающее вычисление Р„выглядит следующим образом (г) — допускающее состоянне автомата Рк). (ро, зг,Хв) !- (Чо, н, 4Хс) 1- (Ч, Е аХс) ) (Р е е) Кроме того, между МО (дс, н, ХвХс) н (г1, е, аХе) все переходы являются переходами автомата Ргв В частности, Хе никогда ие появляется на вершине магазина до достижения МО (д, д аХс)." Таким образом, приходим к выводу, что у Рн есть такое же вычисление, нобезХ, в магазине, те. (гзм н, Хс) /- (г1, е, а).
Итак, Ркдопускаетзс по заключительному л состоянию, т.е. и и ЦР„). ьз 6.2.5, Упражнения к разделу 6.2 6.2.1. Постройте МП-автоматы, допускающие следующие языки. Можно использовать допускание как по заключительному состоянию, так и по пустому магазину— что удобнее; а) (в) (О"1" (н> 1); б) множество всех цепочек из О и 1, в префиксах которых количество символов 1 не больше количества символов О; в) множество всех цепочек из О и 1 с одинаковыми количествами символов О и 1. 4 Хотя а может быть е, н в этом случае Рг опустошает свой магазин н одновременно лопус- 6.2.
ЯЗЬЖИ МП-АВТОМАТОВ 249 6.2.2. (!) Постройте МП-автоматы, допускающие следующие языки: а) (е) (а'!ус ) /=7' или З = з!). Заметим, что этот язык отличается от языка из упражнения 5.1.1, б; б) множество всех цепочек из 0 и 1, у которых количество символов 0 вдвое больше количества символов ! . 6.2.3. (И) Постройте МП-автоматы, допускающие следующие языки: а) (а'!гс ~ з'и) или7 еЦ; б) множество всех цепочек из символов а и Ь, которые не имеют вида згзг, т.е.
не являются повторениями никакой цепочки. 6.2.4. Пусть Р— МП-автомат, допускающий по пустому магазину язык Е = 747(Р), и пусть е И Г.. Опишите, как изменить Р, чтобы он допускал Ь () (е) по пустому магазину. 6.2.5. МП-автомат Р = ((Чо, Чг, Чь Чз.Л, (а, Ь), (Хз. А, В) В, Ча, Хо, (П) имеет следующее определение б. 4кча, а, хз) = (чг, ААх~) б(чз, ь, хз) = (ч„Вхз) б(чз, е, х~) = (7; е) о(Чг, а, А) = (Чь ААА) о(Чг, Ь, А) = (Чь е) 47(Чг, е, Хо) = (Чо, Хо) ЖЧг а В) = (Чз, е) о!4!г, Ь, В) = (Чь ВВ) о(Чг, е, Хо) = (Чо, Ха) б(Чз, Е, В) = (Чг, Е) 4Чз, Е, Хо! = (Чь АХ4) Фигурные скобки опущены, поскольку каждое из указанных множеств имеет только один выбор перехода.
а) (ь) приведите трассу выполнения (последовательность МО), по которой видно, что Ьаб б ЦР)' б) приведите трассу выполнения, показывающую, что аЬЬ б ЦР); в) укажите содержимое магазина после того, как Р прочитал Ь а иа входе; 7 4 г) (!) дайте неформальное описание Е(Р). 6.2.6. Рассмотрим МП-автомат Р из упражнения б.!.1: а) преобразуйте Р в другой МП-автомат Рь допускающий по пустому магазину тот же язык, который допускается Р по заключительному состоянию, т.е. Ьг(Рз) = ЦР); б) постройте МП-автомат Р, такой, что Е(Рг) = !т'(Р), т.е.
Р, допускает по заключительному состоянию то, что Р допускает по пустому магазину. 6.2.7. (!) Покажите; что если Р— МП-автомат, то существует МП-автомат Р,, у которого только два магазинных символа и Е(Рг) = й(Р). Указание. Рассмотрите двоичное представление магазинных символов Р. ГЛАВА б. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 260 б.2.8. (в!) МП-автомат называется ограниченным, если при любом переходе он может увеличивать высоту магазина не более, чем на один символ. Таким образом, если (р, у) содержится в функции переходов, то ф < 2. Докажите, что если Р— МП-автомат, то существует ограниченный МП-автомат Рз, для которого 1,(Рз) = !.(Р).
6.3. Эквивалентность МП-автоматов и КС-грамматик В этом разделе мы покажем, что МП-автоматы определяют КС-языки. План доказательства изображен на рис. 6.8. Цель состоит в том, чтобы доказать равенство следующих классов языков. 1. Класс КС-языков, определяемых КС-грамматиками. 2. Класс языков, допускаемых МП-автоматами по заключительному состоянию. 3, Класс языков, допускаемых МП-автоматами по пустому магазину. Мы уже показали, что классы 2 и 3 равны. После этого достаточно доказать, что соввадаютклассы! и2. Рис. б.В. Оргаэтзация конструкций, показываюэцих эквивалентность трех способов определения КС-языков 6.3П, От грамматик к МП-автоматам По данной грамматике 0 строится МП-автомат, имитирующий ее левые порождения. Любую левовыводимую цепочку, которая не является терминальной, можно записать в виде хАа, где А — крайняя слева переменная, х — цепочка терминалов слева от А, а— цепочка терминалов н переменных справа.
Асс называется остатком (га11) этой левовыводнмой цепочки. У терминальной левовыводимой цепочки остатком является щ Идея построения МП-автомата по грамматике состоит в том, чтобы МП-автомат ими- тнровал последовательность левовыводимых цепочек, используемых в грамматике для порождения данной терминальной цепочки эе. Остаток каждой цепочки Аа появляется в магазине с переменной А на вершине. При этом х "представлен" прочитанными на входе сниволами, а суффикс цепочки эе после х считается непрочитанным. Предположим, что МП-автомат находится в конфигурации (с(,у, Аа), представляющей левовыводимую цепочку хАа.
Он угадывает продукцию, используемую для расши- 251 6.3. ЭКВИВАЛЕНТНОСТЬ МП-АВТОМАТОВ И КС-ГРАММАТИК рения А, скажем, А — ь )3 Переход автомата состоит в том, что А на вершине магазина заменяется цепочкой )х и достигается МО (д,у, )3а). Заметим, что у этого МП-автомата есть всего одно состояние,с). Теперь (сс, у, )За) может не быть представлением следующей левовыводимой цепочки, поскольку )3 может иметь терминальный префикс. В действительности, 13 может вообще не иметь переменных, а у а может быть терминальный префикс. Все терминалы в начале цепочки )3а нужно удалить до появления следующей переменной иа вершине магазина.
Эти терминалы сравниваются со следующими входными символами для того, чтобы убедиться, что наши предположения о левом порождении входной цепочки и правильны; в противном случае данная ветвь вычислений МП-автомата отбрасывается. Если таким способом нам удается угадать левое порождение сг, то в конце концов мы дойдем до левовыводимой цепочки ж.
В этот момент все символы в магазине или расширены (если это переменные), или совпали с входными (если это терминалы). Магазин пуст, и мы допускаем по пустому магазину. Уточним приведенное неформальное описание. Пусть С = ()с, Т, Д, 5) — КС- грамматика. Построим МП-автомат Р = ((с)), Т, (с0 Т, 6, с), 6), который допускает ЦС) по пустому магазину. Функция переходов 6 определена таким образом: 1 о(д, в, А) = ((су, )3) ! А -э 13 — продукция С) для каждой переменной А, 2. 6(с), а, а) = ((с), е)) для каждого терминала а. Пример 6.12. Преобразуем грамматику выражений (см.
рис. 5.2) в МП-автомат. Напомним эту грамматику. 1 -э а ! Ь ! 1а ! (Ь ! 1О ! П Е вЂ” э 1 ! Е " Е ! Е ж Е ! (Е) Множеством входных символов для МП-автомата является ( а, Ь, О, 1, (, ), +, *). Эти восемь символов вместе с переменными 1 и Е образуют магазинный алфавит. Функция переходов определена следующим образом; а) Щ е, Т)= ((су, а),(с?, Ь),(с),)а),(с), РЬ),(сй Ю), (с), П)); б) фс), в, Е) = ((с1, )), (с), Е + Е), (с(, Е * Е), (с), (Е)) ); в) Жд, а, а) = ((сй е) ); асср Ь, Ь) = ((с), в) ); 6(с), О, О) = ((с(, в) ); 6(с), 1, 1) = ((с), а)); 6(),(,О=Нч,е));6(ч,),))= На,г));6(ч,+,+) =((),аН;6(ч,*,*)= Н(,в)!. Заметим, что пункты (а) и (б) появились по правилу 1, а восемь переходов (в) — по правилу 2.
Других переходов у МП-автомата нет. Теорема 6.13. Если МП-автомат Р построен по грамматике С в соответствии с описанной выше конструкцией, то Н(Р) = Е(С). Доказа~ельс~во. Докажем, что и ц Ас(Р) тогда и только тогда, когда ч и ЦС). (Достаточиость) Пусть сг я Е(С). Тогда и имеет следующее левое порождение. 252 ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 5=у~ ~ уз '=Ф ... =Ф уд=ч~ ! ь '"ь Покажем индукцией гю б что (у, и, 5) )- (и, у„а), где у, и а, представляют левовыводимую цепочку у. Точнее, пусть а, является остатком у, и у, = х,а,. Тогда у, — это такая цепочка, что ху, = ю, т.е.
то, что остается на входе после чтения х,. Базис. У, = 5 при 1= 1. Таким образом, х, = л, и у, = в, Поскольку (и, и', 5) )- (д, и', 5) через О переходов, базис доказан. Иидукция. Теперь рассмотрим вторую и последукнцие левовыводимые цепочки. Предположим, что (д, ж,5),'- (с),у„а,) и докажем, что (Н, ж, 5) (- (у, у,, а,. ~). Поскольку а, является остатком, он начинается переменной А. Кроме того, шаг порождения у, ~ у,, включает замену переменной А од/ яии из тел ее продукций, скажем, ф Правило 1 построения Р позволяет нам заменить А ка вершине магазина цепочкой ф, а правило 2 — сравнить затем любые терминалы на мршине магазина со следующими входными символами.
В результате достигается МО (о,у, а,,), которое представляет следующую левовыводимую цепочку у. ь Для завершения доказательства заметим, что а„= л, так как остаток цепочки у„(а она представляет собой ю) пуст. Таким образом, (и, в, 5) )- (и, к, к), т.е. Р допускает и по пустому магазину.
(Необходимость) Нам нужно доказать нечто более общее, а именно: если Р выполняет последовательность переходов, в результате которой переменная А удаляется из вершины магазина, причем магазин под ней не обрабатывается, то из А в грамматике С порождается любая цепочка, прочитанная на входе в этом процессе. Формально: ° если(д,х, А) ~- (с), ц в), тоА ~ х. Доказательство проведем индукцией по числу переходов, совершенных Р. Базис. Один переход. Единственной возможностью является то, что А — э л — продукция грамматики С, и эта продукция использована в правиле типа 1 МП-автоматом Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
