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

была бы применена команда (7), и автомат продолжал бы записывать в магазин вместо того, чтобы сравнивать магазин с лентой, то получился бы вывод (9е, Ьа, ЬаЯ) 1-д (дэ, а, ЬЬаЯ) 3-р~ (де, Л, аЬЬаЕ). Последняя конфигурация в этом выводе характеризуется тем, что входная цепочка прочитана, магазин не пуст, состояние не является заключительным и не применима нн одна команда, т.е. полученная конфигурация (де, Л, аЬЬаЯ) МП-автомата Мэ является тупиковой.

Рассмотренный пример показывает, что МП-автомат может попасть в тупиковую конфигурацию, читая даже „правильную" цепочку, т.е. цепочку, принадлежащую его языку. Это связано с недетерминированностью МП-автомата, т.е. с тем, что иэ данной конфигурации можно непосредственно вывести, 638 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ вообще говоря, более чем одну конфигурацию'. Тот факт, что входная цепочка принадлежит языку МП-автомата, означает лишь, что существует допускающая последовательность конфигураций для этой цепочки, но не всякая последовательность конфигураций, которая возникает при чтении этой цепочки, будет допускающей. Задача эффективного поиска допускающей последовательности конфигураций — одна из основных задач разработки алгоритмов синтаксического анализа на базе МП- автоматов. Как уже отмечалось, основное свойство языков, допускаемых МП-автоматами, состоит в том, что эти языки образуют класс, совпадающий с классом КС-языков.

Но перед тем как доказывать этот основной результат теории МП-автоматов, аналогичный теореме Клини для конечных автоматов, уставновим одно весьма полезное свойство МП-автомата, состоящее в том, что „хвост" входной цепочки и „дно" магазина не влияют на работу МП-автомата с началом входной цепочки и верхом магазина, так как входная цепочка читается строго символ за символом без возвратов и забеганий вперед, а магазин обновляется только сверху.

Приведем строгую формулировку. Теорема 8.5. Пусть в МП-автомате М=©КГ,до РЯо б) на множестве конфигураций для некоторых о, г Е ф х, у Е У' и а,,В й Г' имеет место выводимость (д, хр, сэ) 1-м (г, у,,В). (8.10) "МП-автомат наэывыот деюиерминпрооаииыи, если из каждой его кон~~игурацик непосредственно выводится не более чем одна кокфигурацил. Можно доказать, что, в отличие от конечного автомата, длл МП-автомата невозможна процедура детерминнзации и класс клыков, допускаамъпс детерминированными МП-автоматами, строго вкыочастсл в класс клыков, допускаемых произвольными МП-автоматами.

639 о.4. Магаавааые автоматы Тогда для произвольных а е У', 'у Е Г' имеет место выводимость (9 У д«м( Уа ФУ) (8.11) ~ Индукцией по длине вывода, связывающего конфигурацию (д, ху, а) с конфигурацией (т, у, ~9) в (8.10) докажем, что если эта выводимость имеет место, то имеет место и выводимость (8.11).

Для вывода нулевой длины утверждение тривиально. Пусть доказываемое верно для любой длины вывода, связывающего конфигурацви в (8.10), не превьппиощей п — 1. Предположим, что (д, ху, а) «~м (т, у, ~3). Рассмотрим первый шаг соответствующего вывода. Пусть он имеет вид (д, ах'у, 2а') «-м (д', х'у, оа'), где х = ах', а = Яа', а е У 0 (Ц и Я е Г. Это значит, что на этом шаге применена команда даЯ -~ д'<т. (8.12) Согласно предположению индукции, для произвольных г Е У" и 'у Е Г" имеет место выводимость (д', х'уя, па'у) «" 1 (т, уа,,87). (8.13) Рассмотрим конфигурацию (д, худ, ау) = (д, ах'у», Яа'у) и применим к ней команду (8.12).

Получим (9, ах'У», Яа'7) «м (д', х'Уа, оа'У). Обратно, если для некоторых д, т Е Я, х, у, л Е У" и а, ,В, у Е Г" имеет место выводимость (8.11), то выполняется и выводимость (8.10). 640 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Отсюда в силу (8.13), будем иметь (Ч~ ах рл~ ха 7) ~ (я > х ря~ оп 7) ~ и (г~ ух~ Р7)т т.е. прн выводимости (8.10) за и шагов имеет место и выводимость (8.11) также за н шагов, что и требовалось доказать. Аналогично (но уже индукцией по длине вывода (8.11)) доказываетсл, что если имеет место выводимость (8.11), то имеет место и выводимость (8.10). ~ МП-автомат М называют зниеалентпнььм КС-граммапиасе С, если язык, допускаемый М, совпадает с языком, порождаемым ераммотпиноа С, т.е.

если й(М) = Ь(С). Опишем алгоритм построения по заданной КС-грамматике эквивалентного ей МП-автомата, а также алгоритм построения по заданному МП-автомату КС-грамматики, которой он эквивалентен. Алгоритм построения МП-автомата по КС-грамматике. Для исходной КС-грамматики С = (Р, Ф, о', Р) апре. делим МП-автомат Мс = ((о), У, У ОФ, о, (о), о, б) (с единственным состоянием о), система команд б которого строится следующим образом: для каждого правила А -+ а, принадлежащего Р, в б записывается команда дАА -~ да и для каждого а Е У вЂ” команда оаа -~ дЛ.

Никаких других команд в системе команд б нет. Пример 8.16. Пусть дана грамматика С= ((а, Ь,с), (о'), о', Р), множество правил вывода Р которой есть 8.4. Магазиввые автоматы Тогда эквивалентный ей МП-автомат задается следующей системой команд: дЛЯ ~ даЯЬБ~даЯ~ дс, даа -+ дЛ, дбЬ -+ дЛ, дсс-> дЛ (мы использовали сокращенную запись нескольких команд с одинаковыми левыми частями по аналогии с тем, как мы это делаем при записи множества правил вывода грамматики).

В системе команд МП-автомата, который строится по заданной КС-грамматике так, как это описано вьппе, мы видим два „сорта" команд: 1) команды, „моделирующие" применение правил, исходной грамматики (в данном примере это команды первой строки); при выполнении каждой такой команды МП- автомат делает Л-такт, т.е. не продвигает головку по входной ленте; 2) команды „сравнения", согласно которым МП-автомат должен убирать верхний символ магазина всякий раз, когда он совпадает с обозреваемым символом на ленте. Тогда, читая входную цепочку, такой МП-автомат „моделирует" левый вывод этой цепочки в исходной грамматике, применяя каждый раз, когда верхним символом магазина оказывается нетерминзл, команду „первого сорта" и всякий раз, когда верхним символом магазина оказывается терминал исходной грамматики, „команду сравнения".

Прочитаем цепочку аасбс: (д, аасбс, Я) 1- (д, аасбс, аБЬБ) 1- (д, асбс, ЯЬЯ) ~- 1- (д, асбс, аЯЬБ) 1- (д, сбс, ЯЬЯ) ~- (д, сЬс, сбЯ) ~ ~ (д, Ьс, ЬЯ) ~ (д, с, Я) ~- (д, с, с) 1- (д, Л, Л). Нетрудно видеть, что этот вывод „моделирует" левый вывод в грамматике: Я ~- аЯЬЯ ~- ааБЬЯ ~- аасбЯ 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. '/2 21' 644 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ а окончательно (д, х, А) $-' (д, Л, Л).

Следовательно, если х Е Ь(С), то о Е' х и (д, х, о) $-' (д, Л, Л), т.е. х Е ЦМа). Итак, мы доказали, что Ь(О) С Ь(Ма). Чтобы доказать обратное включение, сначала индукцией по длине п вывода на множестве конфигураций МП-автомата Мс докажем, что (ч, х, А) «-м (д, Л, Л) влечет А ~с х (для произвольных А Е Ф и х Е У*). Пусть о=1, т.е. (д, х, А) ~-(д, Л, Л). Согласно построению МП-автомата МО, зто может быть тогда и только тогда, когда х Е У и А = х, т.е. х ~' х.

Пусть доказываемое верно для любого и < т — 1, где гп < 2, и (д, х, А) ~-~ (о, Л, Л), (8.14) причем первыи шаг соответствующего вывода имеет вид (д, х, А) 1- (д, х, Х1Хз...Хь). (8.15) (ц, х, Х1Хг...Хь) ~ (д, Л, Л). (8.16) Используя индукцию по длине магазинной цепочки Х1Хз... Хь, можно доказать, что из (8.16) следует существование таких Это значит, что в системе команд б есть команда дЛА -+ -+ дХ1ХзХь и, следовательно, правило в множестве правил вывода Р грамматики С есть правило А -+ Х1Хг...Хы по которому указанная команда построена.