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

)-~а-1 (з, м х „Х,) ~-~в (г, Л, Л), где для любого 4 = 1, й выполняется 0 < ш; < тп — 1. Поэтому в силу теоремы 8.5 для любого з = 1, я — 1 (з; и х;, Х;) 1-ом (з;, Л, Л), где зе = р, а зз = г, и, согласно предположению индукции, [з; 2Х;з;] 1-*х;. Следовательно, согласно построению грамматики Сзз, имеет место выводимость [ЧЯт] 1-см о[рХ4з4][з4Х2з2] ° ° ° [за — 1Хат] ~ с. ах1х2... ха = ау = х, что и требовалось доказать. Пусть цепочка х допускается МП-автоматом М.

Тогда где ду Šà — одно вэ эаключительных состояний МП-автомата М. Согласно только что докаэанному, в этом случае для гРамматики 624 выполнаетсЯ [озЯеЕ] ~о х. Но так как в множестве правил вывода грамматики с424 есть правило Я-+ -~ [деЯеду], то мы получим Я~а [деЯзду] ~~ х, т.е. х е Цбзз). Итак, ЦМ) С Ь(СЗ4).

Для доказательства обратного включения докажем сначала, что[дЯг]1-~ хвлечет(д, х, Я)~-м(т, Л, Л) длялюбыхо,гбао, х Е У' и Я е Г. Снова проведем индукцию по длине вывода (в грамматике См). При ~д2г] 1- х получаем правило [дЯг] -+ х в Р и, следовательно, команду дхЯ вЂ” ) тЛ в о, т.е. (д, х, Я) Цг, Л, Л). 652 8. КОНТЕКСТНО-СВОБОДНЫЕ НЗЫКИ Если же [юг] Р" х для некоторого гп > 1, то х = ау для неко- торого а Е 7 0 (Л) и [дЯг] 1- а[рХ1 з1] [з1Хзз2]... [зз 1Хьг], причем для всех 1 = 1, Й [я-1Х1за] ~ хб где зз = р, зь = т и 1 < в; < и — 1, так что у = х1хг .. хз. Согласно предположению индукции, тогда для каждого такого з (з; мх;,Х;) ~-' (з;,Л,Л).

Но так как указанный вьппе первый шаг вывода в грамматике возможен только при наличии команды в МП-автомате даЯ -~ -+рХ1Хз...Хь, то (д, х, Я) 1- (р, р, Х|Хз... Хь) ~-* )-' (зм х2 ..хь Хг .. Хь) ~-' ~-' (з, х, Хь) ~-' (, Л, Л). Если теперь цепочка х порождается грамматикой С, т.е. з 1-О х, то первый шаг вывода х из о, согласно определению системы правил грамматики См, будет иметь вид о ~- [дзгз~,] для некоторого ду Е Р, и, следовательно, [доведу] ~-О х.

Тогда в силу только что доказанного (дз, х, Яе) ~-м (ду, Л, Л), т.е. х е Е ЦМ). Итак, ЦСм) С ЦМ), а поскольку обратное включение уже доказано, то Цм) = Ь(См) ~ Из доказанных теорем 8.6 и 8.7 получаем следующую теорему. Теорема 8.8, Язык является контекстно-свободным тогда и только тогда, когда он допускается некоторым МП-автоматом. Замечание 8.10. Существует одна полезная модификация построения МП-автомата по КС-грамматике. Вернемся 653 8.4. Магаэвввме аатаматм к примеру 8.16.

Можно заметить, что в этом примере правая часть каждого правила грамматики начинается некоторым терминалом. Учет этой особенности позволяет найти другой МП-автомат, который, как нетрудно показать, тоже эквива лентен данной грамматике. Система команд этого автомата имеет следующий вид: даЯ вЂ” ~ дЯЬЯ~дЯ, дсг-+ ДЛ, Чаа~дЛ, ~ЬЬ~~Л, асс -+ оЛ. Его преимущество в том, что он „видит" первый непрочитанный символ входной цепочки и, следовательно, имеет меньше альтернатив при выборе команды: например, если очередной символ есть Ь, то ни одна иэ команд первых двух строк не может быть применена. Тогда этот автомат имеет меньше воэможностей попасть в тупик.

В общем случае, если правая часть любого правила грамматики имеет вид а~, где а Е У, МП-автомат, эквивалентный данной грамматике, определяется командами вида даА -~ д~, оЬЬ~дЛ, Ье7; (первая — для правила А -+ ас). В такой модификации МП- автомат записывает в магазин „хвост" правой части правила, следующей эа первым терминалом. Можно доказать, что любая КС-грамматика может быть определена правилами такого вида (так называемая нормальная форма Грейбах"). 'См:.

Аао А., КвмакДж. .