Магазинные автоматы, страница 4

Из (8.14) и (8.15) следует, что имеет место выводимость о.4.Магаэннные автоматы входных цепочек хм хз, ..., хы что х = х1хо... ха и имеет место выводимость (д, х|х2... ха, Х1 Хо... Ха) «~' «~' (д, хз".хы Хз...ха) «~' «ж (Чхз аХ Ха)«ж «'а"-' (д,ха,ха) «~' (д,л,л) (8.17) для некоторых т;, таких, что 1 < т; < еп — 1, 1 = 1, Й.

Вывод (8.17) можно прокомментировать так: чтобы достичь заключительной конфигурации, Мо должен выбросить все символы Х1, Хо,, Ха из магазина. Предположим, что к тому моменту, когда Х1 покинет магазин (чтобы уже больше туда не вернуться!), будет прочитано некоторое начало входной цепочках — цепочка х1,когда Хз покинет магазин, будет прочитана следующая подцепочка хо и так до тех, пока наконец, автомат не прочитает цепочку хь — конец цепочки х.

Из теоремы 8.5 следует, что существуют также выводы (7, „х,)«7;л;л, (д, хг, Хз) «~е (д, Л,Л), (8.18) И, х, х ) «™" И, л, л). Все числа тп; при 4 = 1, й не больше гп — 1. Тогда согласно предположению индукции, из (8.18) следует, что для каждого 4 = 1, й в грамматике С имеет место Х; «~ х;, и в силу того, что в Р есть правило вывода А — ~ Х1 Хз... Ха (см. (8.15)), А «Х1ха... Ха «' х1хг... ха = х, т.е. А «~ х, что и требовалось доказать. Отсюда, если х Е й(Мс), то х Е ЦС), т.е. ЦМс) С ЦС), и в силу доказанного выше языки Ь(С) и Ь(Мо) совпадают. ~ь Алгоритм построения КС-грамматики по МП-автомату. Дадим сначала неформальную мотивировку той конструкции, которал будет приведена ниже.

Будем рассматри- 646 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ вать МП-автомат как „игрока", ставящего цели следующего вида: „находясь в состоянии о и имея верхний символ магазина Я, перейти в состояние я". Условимся записывать такую цель в виде тройки [4Яя]. Как может наш „игрок" достичь поставленной цели? Если в множестве команд автомата („правил игры") есть команда даЯ -+ гХ1Хг... Хь, где для каждого з Х; — магазинный символ (Х; Е Г), то после выполнения этой команды МП-автомат перейдет в состояние г.

Если г = з, то цель достигнута, иначе ставим цель (гХ1л1], а достигнув ее, ставим цель (я1Хззг] и т.д. Достигнув цели (зь 1Хьз], „игрок" достигает и цели (дЯя]. Так как рассматривается допуск с пустым магазином, то символы Х; должны по очереди покинуть магазин, и только в этом случае может быть достигнута „глобальная" цель МП-автомата: (доЯеду], ду Е Р („находясь в начальном состоянии и имея верхним символом магазина начальный магазинный символ, попасть в одно из заключительных состояний, опустошив магазин").

Так как, вообще говоря, „игрок" не знает наперед последовательности состояний зм в2, ..., яь м ведущих к цели, он должен перебрать все такие последовательности. Эти неформальные соображения лежат в основе следующей конструкции. Пусть дан МП-автомат М=(Я, К Г, де~ г~ ~е, о). Определим КС-грамматику См = (К, Ф, о', Р), терминальный алфавит которой совпадает со входным алфавитом МП-автомата М, следующим образом. Нетерминальный алфавит Ф грамматики есть множество, находящееся во взаимно однозначном соответствии с множеством всех упорядоченных троек вида (д, Я, я), где д, л Е Ч, Я Е Г, пополненное символом о', не принадлежащим ни одному из множеств ф Р', Г и объявляемым аксиомой грамматики. 8.4.

Магвэвивые автоматы 647 Упорядоченные тройки указанного вида записывают обычно как [дЯв], интуитивно понимая каждую такую тройку как охарактеризованную вьппе цель. Таким образом, Ф = ([дЯв]: д, в Е Я н Я Е Г) 0 (Я). Множество правил вывода Р грамматики См строится так: а) если команда даЯ ~ тХ1Хз... Хо, Ь > 1, принадлежит системе команд 6, то в Р записываются все правила вида [дЯва] ~ а[тХ1 в1][в1Хгве]... [вв 1Хова] для любой последовательности й состояний вм ..., ва множества Я (тем самым к Р добавляется Я" правил на каждую команду указанного вида); б) для каждой команды даЯ -+ тЛ в б в Р добавляется правило [дЯт] -+ а; в) для каждого ду Е Р в Р вводится правило Я -+ [доЯоду]; г) никаких других правил в Р, кроме определенных пп.

а-в, нет. Пример 8.17. Для МП-автомата М=((до В,а), (а, Ц, (а, Ь Я) до (яо), Е, Ь) с множеством команд б, имеющих внд 6оа~ ~ данае', д1аа -+ д1аа, д1Ьа -+ аЛ, чзьа + чзл ~,лг д,л, 6оЛя- о Л, построим эквивалентную ему КС-грамматику. Можно доказать, что этот МП-автомат допускает язык (а"Ь": п > О). Заметим, что МП-автомат М допускает пустую цо1почку, применяя к начальной конфигурации (до,Л,Я) последнюю коман- 648 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ ду. Построеннал по данной системе команд грамматика будет иметь следующий вид: ~ -+ [до~до] [деляг] — д а[ддазд][здезг], зд,зг е (де, дд> дг), [ддаз2] -+ а[ддаздИздаз2], змз2 е Йо, дм дг), [ддадг] д Ь, [д ад]- Ь, [дгядо] + Л [де~до] -+ л.

Подчеркнем, что во второй и третьей строчках имеется не по одному, а по 32 = 9 правил (число всех последовательностей двух состояний из трехэлементного множества состояний). Выведем в этой грамматике цепочку ааЬЬ: 8 ~ [до~до] ~ а[ддадг][дг~до] ~ аа[ддадг][дгадг][дг~до] ~ ~- ааЬ[дгадг][дгЕдо] ~- ааЬЬ[дг~до] ~- ааЬЬ.

На втором шаге этого вывода мы применяем то правило вывода ю девяти правил второй строки, которое получается при подстановке вместо зд состояния дг, а вместо зг состояния де. Мы „угадываем" эти состояния, знал (по системе команд исходного МП-автомата), что достичь заключительного состояния по прочтении (непустой) входной цепочки наш МП-автомат может только из состояния дг. В то же время, если бы мы на втором шаге использовали правило второй строки, получающееся подстановкой зд = дд, зг = дг, возник бы бесполезддмдД нетермииал [ддадд] и наш вывод зашел бы в тупик. Аналогично на третьем шаге используется то правило ю девяти правил третьей строки, в котором зд = зг = дг.

После этого применяем по очереди правила четвертой, пятой и шестой строк, завершая вывод. Если мы теперь в построенном выводе „считаем" по шагам магазинные символы, заключенные в квадратных скобках 8А. Магазяавые автоматы между состояниями, то получим Я, аЯ, вам, аЯ, Я, т.е. получим изменение содержимого магазина (не считая последнего шага, когда происходит его окончательное опустошение), представленное в следующем выводе на множестве конфигураций МП-автомата М: (дв, ааЬЬ, 2) 1- (щ, а66, аЯ) ~- (дм ЬЬ, ааЕ) 1- 1-(дэ, Ь, аЯ)~-(а, Л, Я)~(Чо, Л, Л).

Этот вывод есть не что иное, как допускающая последовательность конфигураций для цепочки аа66. Читая же последовательности состояний в квадратных скобках, мы получим в итоге ту последовательность состояний, которую проходит МП-автомат, допуская написанную выше цепочку. Действительно, после первого шага вывода в грамматике получим последовательность дв, дв, что можно интерпретировать так: „из состояния вв перейти (вернутьсл) в это же состояние дв,прочитав входную цепочку".

После второго шага будем иметь дв, в1, а, дв, что означает: „чтобы вернуться в дв, сначала нужно попасть в дэ через в1"). После третьего шага получим дв, дм Чм а, чь до. Это и есть результирующая последовательность состояний, так как все следующие шаги МП-автомата связаны с „выталкиванием" символов из магазина и не приводят к возникновению новых целей. ф Как правило, грамматика, которая указанным вьппе способом строится по МП-автомату, оказывается очень громоздкой, содержит много бесполезных и нвдостпижиммя символов. Это связано с тем, что в ней фигурируют произвольные последовательности состояний МП-автомата фиксированной длины. Что касается разобранного примера 8.17, то в этом случа|е легко написать грамматику для языка (авЬ": и ) О) непосредственно: Ю вЯЬ! вЬ! Л.

650 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ По этой грамматике можно построить МП-автомат, используя алгоритм кз первой части доказательства основной теоремы, значительно более простой, чем исходный. Его система команд будет иметь следующий вид: даю-Ф доЬ! дь, даа -+ дЛ, дЬЬ-+ дЛ, дЛЯ -+ дЛ. В общем же случае проблема распознавания эквивалентности двух МП-автоматов (в отличие от такой же проблемы для конечных автоматов) не разрешима, и не существует общего алгоритма „упрощения" (в определенном смысле, „минимизации") МП-автомата, хотя, как мы только что видели, в конкретных случаях зто вполне возможно.

Теорема 8.7. МП-автомат М эквивалентен грамматике См. ~ Индукцией по длине и вывода в М докажем, что Я Е Г, (д, х, 2) 1-" (г, Л, Л) для любых д, гбао, хЕ У' влечет (дЯг] 1-"х в См. Если и = 1, т.е. (д, х, Я) $- (г, Л, Л), то я Е У 0 (Л1, и в Ю есть команда дух -~ гЛ, откуда в Р есть правило (д2г] -+ к, и [дЪ.] 1- *. Пусть доказываемое верно для каждого и < т — 1, где ва ) 1, и пусть (д, х, 2) 1-~ (г, Л, Л), причем первый шаг соответствующего вывода имеет вид (д, х, Я) ~- (р, у, Х1Хз...Хь), где х = ау для некоторого а Е У 0 (Л1. Аналогично доказательству теоремы 8.6 (см. (8.17)) доказывается, что тогда найдутся такие цепочки я1хз... яь и такая 651 В.4.Магазвивые автоматы последовательность состояний за, ..., зь и что у = х1хэ...ха и (р, х1х2" ° хь Х1Х2...Ха) 1 ~~ (зм х2 ° ° ° хь Х2 ° " Ха) ~ ~~ 1- м ...