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