XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 101
Текст из файла (страница 101)
Прочитаем цепочку аасЬс: (д, аасЬс, Я) 1- (д, аасЬс, аБЬБ) 1- (д, асЬс, ЯЬЯ) ~- 1- (д, асЬс, аЯЬБ) 1- (д, сЬс, $6$) ~- (д, сЬс, с6Я) ~ ~ (д, Ьс, ЬЯ) ~ (д, с, Я) ~- (д, с, с) 1- (д, Л, Л). Нетрудно видеть, что этот вывод „моделирует" левый вывод в грамматике: Я ~- а$6$~- ааБЬЯ~-аас6$1- аасбс, 642 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ т.е.
МП-автомат, строя допускающую последовательность конфигураций для входной цепочки, на каждом шаге, когда верхний символ магазина не совпадает с очередным символом входной цепочки, должен „угадать" применяемое правило (выбрать в данном примере одну иэ трех первых команд). Неправильный выбор приведет к тупику, например: (д, аасЬс, о) ~- (о, аасЬс, ао) ~ (с, асЬс, о) 1- (о, асйс,с).
Докажем, что рассмотренный алгоритм дает МП-автомат, эквивалентный исходной КС-грамматике. Теорема 8.6. МП-автомат Мс эквивалентен КС-грамматике С. ~ Индукцией по длине п вывода тперминальноб цепочки х из нешерминала А докажем, что если А ~-О х, то (д, х, А) 1 мс (д Л Л) Пусть п = 1, т.е. А 1-1 х; тогда в Р есть правило А -~ х и, следовательно, в о есть команда дЛА -> дх. В таком случае при х = Л имеет место выводимость (о, Л, А) 3- (о, Л, Л), и требуемый вывод на множестве конфигураций МП-автомата Мс построен.
Если же цепочка х непустая, то тогда, расписывая ее по символам, т.е. полагая х = х(1)... х(й), й > 1, получим (о, х(1)...х(й), А) 1- (о, х(1)...х(й), х(1)...х(й)). Из последней конфигурации за й шагов посредством применения команд вида оаа -+ оЛ, где а Е У, выводится конфигурация (о, Л, Л), и, таким образом, (о, х, А) ~-~*~+1 (о, Л, Л). Пусть теперь доказываемое верно для любого и, не превосходящего некоторого гп — 1 для т > 2, пусть А ~ х и первый 643 В.4.Магазинные автоматы шаг вывода длины гп цепочки х из нетерминала А имеет вид А 1- Х1Хч...
Хю где й > 1 и для каждого 4 = 1, й символ Х, есть символ объединенного алфавита грамматики'. Далее, из цепочки Х1 Хт... Хь должна быть выведена терминальная цепочка х. Это значит, что для каждого 4 = 1, й иэ символа Х; выводится какая-то подцепочка цепочки х (в частности, если этот символ является терминалом, он будет одним из символов цепочки х). Таким образом, для каждого с = 1, й выполняется Х; ~-еч х; (гпс ~ )0), и и = х1ХЗ... Хь. Для Х, Е М длина вывода гас подцепочки х; не может превьппать гп — 1.
Следовательно, согласно предположению индукции, имеем (д, х,, Хс) $-" (д, Л, Л), а для Х; Е У (гас = 0 и, следовательно, Х; = х;), согласно построению МП-автомата Мп, Тогда в силу теоремы 8.5 (о, х1хз...хь, Х1Хз...Хь) ~-' (д, хз... хю Хз... Хь) ~' $-" (д, хы Хй) Е- (д, Л, Л). Кроме того, так как А 1- Х1Хз...ХЫ то в Р есть правило вывода А-~ Х1Хз...Хю откуда, согласно построению МП- автомата Ма, в б есть команда дЛА -+ дХ1Хг ". Хь и (д, х, А) 1- (д, х, Х1Хз...Хе), ' Цепочка Хс Хе...
Хь ке может быть пустой, так как тою)да она окажетсе последней цепочкой рассматриваемого вывода и его длина будет равна 1, а мы предшиожили, что его длина равна юл > 1. 644 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ а окончательно (д, х, А) $-' (о, Л, Л). Следовательно, если хек(С), то о Е' х и (д, х, о) $-' (о, Л, Л), т.е. х Е ЦМа). Итак, мы доказали, что Ь(О) С Ь(Ма). Чтобы доказать обратное включение, сначала индукцией по длине п вывода на множестве конфигураций МП-автомата Мс докажем, что (ч, х, А) 1-мо (д, Л, Л) влечет А ~с х (для произвольных А Е Ф и х Е У*).
Пусть о=1, т.е. (д, х, А) ~-(д, Л, Л). Согласно построению МП-автомата МО, зто может быть тогда и только тогда, когда х Е У и А = х, т.е. х ~' х. Пусть доказываемое верно для любого и < т — 1, где гп < 2, и (д, х, А) ~-~ (о, Л, Л), (8.14) причем первыи шаг соответствующего вывода имеет вид (д, х, А) 1- (д, х, Х1Хз...Хь). (8.15) (о, х, Х1Хг...Хь) ~ (о, Л, Л). (8.16) Используя индукцию по длине магазинной цепочки Х1Хз...
Хь, можно доказать, что из (8.16) следует существование таких Это значит, что в системе команд б есть команда дЛА -+ -+ дХ1ХзХь и, следовательно, правило в множестве правил вывода Р грамматики С есть правило А -+ Х1Хг...Хы по которому указанная команда построена. Из (8.14) и (8.15) следует, что имеет место выводимость о.4.Магаэннные автоматы входных цепочек х1, хз, ..., хы что х = х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 ~ [до~до] ~ а[ддадг][дг~до] ~ аа[ддадг][дгадг][дг~до] ~ ~- ааЬ[дгадг][дгЕдо] ~- ааЬЬ[дг~до] ~- ааЬЬ. На втором шаге этого вывода мы применяем то правило вывода ю девяти правил второй строки, которое получается при подстановке вместо зд состояния дг, а вместо зг состояния де. Мы „угадываем" эти состояния, знал (по системе команд исходного МП-автомата), что достичь заключительного состояния по прочтении (непустой) входной цепочки наш МП-автомат может только из состояния дг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
