Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 58
Текст из файла (страница 58)
Взтомслучаех= к, и А ~ а Индукции. Предположим, что Р совершает и переходов, где и > 1. Первый переход дщжен быть типа 1, где переменная А на вершине магазина заменяется одним из тел ее продукций. Причина в том, что правило типа 2 может быть использовано, когда на вершине магазина находится терминал. Пусть использована продукция А — > У,У,...Уь где мждый У, есть либо терминал, либо переменная.
В процессе следующих и — 1 переходов Р должен прочитать х на входе и вытолкнуть Уь Уь, Уь из магазина по очереди. Цепочку х можно разбить на подцепочки х~хз...хь 253 6.3. ЭКВИВАЛКНТНОСТЬ МП-АВТОМАТОВ И КС-ГРАММАТИК где х, — порция входа, прочитанная до выталкивания У, из магазина, т.е. когда длина магазина впервые уменьшается до А — !. Тогда х, является следующей порцией входа, читаемой до выталкивания Уь и т.д. На рис. 6.9 представлены разбиение входа х и соответствующая обработка магазина.
Предполагается, что )3 имеет вид ВаС; поэтому х разбивается на три части хчхгхл где х, = а. Заметим, что вообще, если У, — терминал, то х, также должен быть терминалом. к кг "з Рис. 6.9. л(Повтомат А прочитывает х и удаляет ВаС иг своего магакиио Формально мы можем заключить, что (с), х,х,. ь ..хь У) )- (с), х,,...хь е) для всех 1 = 1, 2, ..., к. Кроме того, длина ни одной из этих последовательностей переходов не превышает и — 1, поэтому применимо предположение индукции в случае, если У, — перемен- ная.
Таким образом, можно заключить, что У, » хе Если У, — терминал, то должен совершаться только один переход, в котором прове- ряется совпадение х, и У,. Опять-таки, можно сделать вывод, что У, » х„на этот раз порождение пустое. Теперь у нас есть порождение А» Учу,... 1'е» хууг... Уе» ... » х,хг...хе Таким образом, А» х.
Для завершения доказательства положим А =В н х=и. Поскольку нам дано, что и н А(Р),то(д, ге,В) )- (су, я,е). По доказанному индукциейимеем б» н,т.е. н и Цб). П ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 254 ,' 6.3.2. От МП-автоматов к грамматикам Завершим доказательство эквивачентностн, показав, что для любого МП-автомата Р найдется КС-грамматика О, язык которой совпадает с языком, допускаемым Р по пустоиу машзину. Идея доказательства основана на том, что выталкивание одного символа из иягазина вместе с прочтением некоторого входа является основным событием в процессе работы МП-автомата.
Прн выталкивании из магазина МП-автомат может изменять шее состояние, поэтому нам следует учитывать состояние, достигаемое автоматом, когда он полностью освобождает свой магазин. у, Уе х «з Рис. 6! П. МУ-автомат совершает последовательности переходов, в резулыпате которых символы по одному удшзяются из магазина На рис.6.10 показано, как последовательность символов У„уь ..., Ул удаляется из иагазина. До удаления У, прочитывается вход хп Подчеркнем, что это "удаление" являепя окончательным результатом, возможно, многих переходов.
Например, первый перезсд может изменить у, на некоторый другой символ у, следующий — изменить а на сЛ; дальнейшие переходы — вытолкнуть О; а затем И Окончательный результат заключается в том, что у~ изменен на ничто, т.е. вытолкнут, и все прочитанные к этому моменту вкодные символы образуют х,. На рис. 6ПО показано также окончательное изменение состояния.
Предполагается, чш МП-автомат начинает работу в состоянии ре с У, на вершине магазина. После всех переходов, результат которых состоит в удалении Уп МП-автомат находится в состоянии Рн Затем он достигает окончательного УдалениЯ Уь пРочитываЯ пРи этом х и пРиходЯ, возможно, за много переходов, в состояние рз. Вычисление продолжается до тех пор, пои каждый из магазинных символов не буде~ удален. 6.3. ЭКВИВАЛЕНТНОСТЬ МП-АВТОМАТОВ И КС-ГРАММАТИК 255 Наша конструкция эквивалентной грамматики использует переменные, каждая из которых представляет "событие", состоящее в следующем. 1. Окончательное удаление некоторого символаХиз магазина.
2. Изменение состояния от некоторого р (вначале) до д, когда Х окончательно заменяется к в магазине. Такую переменную обозначим составным символом [РХс1). Заметим, что зта последовательность букв является описанием одной переменной, а не пятью символами грамматики. Формальное построение дается следующей теоремой. Теорема 6.14. Пусть Р = Я,.ь, Г, б, дв 2,) — МП-автомат. Тогда существует КС- грамматика О, для которой ЦО) = Х(Р). Доказательство. Построим 0 = (У, з„гс б), где Усостоит из следующих переменных. 1.
Специальный стартовый символ б. 2. Все символы вида[рХ~(), гдер ид — состояния изб, аХ вЂ” магазинный символ из Г. Грамматика С имеет следующие продукции: а) продукции 6-э [д,2„Р) для всех состояний Р. Интуитивно символ вида [д02ор[ предназначен для порождения всех тех цепочек н, которые приводят Р к выталкиванию 2 из магазина в процессе перехода из состояния ~, в со- стояние Р. Таким образом, (и, м, Еч) [- (д, к, я).
Эти продукции гласят, что стартовый символ 5 порождает все цепочки н, приводящие Р к опустошению магазина после старта в начальной конфигурации; б) пусть фд, а, Х) содержит пару (»,?;Уз... Уз), где а есть либо символ из Х, либо а, а к — некоторое неотрицательное число; прн 1= 0 пара имеет вид (г, с). Тогда для всех списков состояний гь гь ..., гя в грамматике С есть продукция [юг~) — э а[гУ,гфг,уя ~)...[г„уу~гД. Она гласит, что один из путей выталкивания Х и перехода из состояния д в состояние гя заключается в том, чтобы прочитать а (оно может быть равно к), затем использовать некоторый вход для выталкивания У~ из магазина с переходом из состояния г в состояние гь далее прочитать некоторый вход, вытолкнуть У, и перейти из г~ в гз, и т.д. Докажем корректность неформальной интерпретации переменных вила [~(ХР]: ° [ЯХР)» м тогда и только тогда, когда(д, зг,Х) [- (р, к, в). (Достаточность) Пусть ( у, и, Х) [- (Р, я, а).
Докажем, что [ДАХР) =» и, используя индукцию по числу переходов МП-автомата. ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 256 Базис. Один шаг. Пара (и, в) должна быть в б(д, ш, Х), и и есть либо одиночный символ, либо ж Из построения С следует, что [г)Хр] » и является продукцией, поэтому [ДАХР] ~ »г. Иидукция. Предположим, что последовательность (д, »г, Х) [- (р, в, а) состоит из и переходов, и л > 1.
Первый переход должен иметь вид 0), и', Х) [ — (г», Х Уг У ... У») ]- (р, в, л), тле и = аХ для некоторого а, которое является либо символом из Х, либо а Отсюда следует, что пара (г», Ур?> .. Уд) лолжиа быть в б(г), а, Х). Кроме того, по построению б существует продукция [юг»] — » а[г, Урз][г, Угг,]... [г»,У»гг], у которой г» = р и гь г,, гг > — некоторые состояния из Д. На рис.
6.10 показано, что символы Уь Уь ..., У» удаляются из магазина по очереди, и зля 1= 1, 2, ..., Й вЂ” 1 можно выбрать состояние р„в котором находится МП-автомат при удалении У,. Пусть Х= влг>..иь где и; — входная цепочка, которая прочитывается ло удавил У, из магазина. Тогда (»,, и „У) ]- (г„л, 6). Поскольку ии одна из указанных последовательностей переходов ие содержит более, чем л переходов, к ним можно применить предположение индукции. Приходим к выво- лу, что [г,,уг,] =» и;. Соберем эти порождения вместе. [ЛХг»] =» а[г»у~г~][г~ Уггг]... [гь, У»г»] =» шг~[г~ук»]. [гг ~У»г»! =» аи,юг[г»У»гз]...[гь,У»г»] =» аз»ля>..и~я = и~ Здесы; =)».
(Необходимость) Доказательство проводится иидукцией по числу шагов в порождении. Базис. Один шаг. Тогда [ДАХР] -+ и должно быть продукцией. Единственная возможность для существования этой продукции — если в Р есть переход, в котором Х выталкивается, а состояние д меняется иа р. Таким образом„пара (р, я) должна быть в 4д,а,Х), па= и. Но тогда(п,з»,Х) [- (р, в, 6). Иидукция. Предположим, что [ДАХР] ~ »г за и шагов, где п > 1. Рассмотрим подробно первую выводимую цепочку, которая должна выглядеть следующим образом. [юг»] =» и[г»уг~][г~узгг]...[гь,у»гг]»»г Здесь гг = р.
Эта продукция должна быть в грамматике, так как (»„, У,У,... У») есть в фд, а, Х). 6.3. ЭКВИВАЛЕНТНОСТЬ МП-АВТОМАТОВ И КС-ГРАММАТИК 257 Цепочку и можно разбить на и = глг,ил ..и ~ так, что (г,,уг ) =ь и) для всех 1= 1, 2, . я — 1. По предположению индукции для всех этих 1 верно следующее утверждение. (г, ь и'„У,) г- (и, е, в) Используя теорему 6.5 лля того, чтобы поместить нужные цепочки вокруг ю, на входе и под У, в магазине, получим (г, ь и~,ж,-ь ..ми У,У,, ь .. Уь) (- (г„и, ь ..ив У,.ь ..У~).
Соберем все зти последовательности вместе и получим следующее порождение. (с7,ав,н;...згь.Х) ~ (го,згРгг."иь ~суп..Уя) (- (г~ ичи ь..1гь Узун., Уь) ( (гз жп..ни Уь .. Уь) ( ... (- (гь ж а) Поскольку г~= р, мы доказали, что (д, и, 1) (- (Р, а, в). Завершим доказательство. 5 =~ и тогда и только тогда, когда [<угря) =ь и для некоторого р в соответствии с построенными правилами для стартового символа 5. Выше уже доказано, что (деУРД =» и тогда и только тогда, когда (д, ж, ~,) (- (Р, а, в), т.е. когда Р допускает и по пустому магазину. Таким образом, ь(0) = Х(Р).
П Пример 6.15. Преобразуем в грамматику МП-автомат Ря= ((ф, (б е), (с), Бм д, 2) из примера 6.!О. Напомним, что Ря допускает все цепочки, которые нарушают правило, что каждое е (еВе) должно соответствовать некоторому предшествующему 1(1(). Так как Ря имеет только одно состояние и один магазинный символ, грамматика строится просто. В ней есть лишь следующие две переменные: а) 5 — стартовый символ, который есть в каждой грамматике, построенной методом теоремы 6.14; б) (с(Ъ(] — единственная тройка, которую можно собрать из состояний и магазинных символов автомата Рь. Грамматика 0 имеет следующие продукции. 1. Единственной продукцией для 5 является 5 — ь (~(Щ.
Но если бы у МП-автомата было п состояний, то было бы и и продукций такого вида, поскольку последним может быть любое из и состояний. Первое состояние должно быть начальным, а магазинный символ — стартовым, как в нашей продукции выше. 2. Из того факта, что Б,(с(, Ь 2) содержит(у,22), получаем продукцию (дЪ)) — э 1(дЩ[уЩ. В атом простом примере есть только одна такая продукция. Но если 'бы у автомата было и состояний, то одно такое правило порождало бы и' продукций, поскольку как промежуточным состоянием в теле, так и последним состоянием в голове и теле могли быть любые два состояния. Таким образом, если бы г и р ГЛАВА 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
