XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 105
Текст из файла (страница 105)
х(й). Нетерминая же [ааг] при а Е У может быть, по определению, заменен терминалом а тогда и только тогда, когда в системе команд б конечного автомата М есть команда аа ~ г, т.е. из состояния д по символу а можно перейти в состояние г. При таком определении грамматики 0' она породит непустую терминальную цепочку х тогда и только тогда, когда х порождается грамматикой 6 и читается на некотором пути из на чального состояния в одно из заключительных, — именно тогда (и только тогда) иэ цепочки [дэх(1)в1][з1х(2)вэ]... [вз ~х(й)ду] может быть выведена сама цепочка х = х(1) х(2)... х(я). Образно говоря, грамматика С' каждый символ непустой цепочки х, порождаемой грамматикой С, помещает между двумя „стражами" — состояниями конечного автомата, и символ может избавиться от этих „стражей" тогда и только тогда, когда в конечном автомате М есть переход по нему из первого состояния во второе.
Дадим теперь формальное определение грамматики С'. а' = (р; ж', У, Р ), где Ф' = [[юг]: д, г Е 1з и Х Е 'г' 0 Ф) 0 (У), У Ф 1Г 0 Ф (аксиома грамматики С'), а множество правил вывода Р' строится следующим образом: 1) правило вывода У вЂ” ~ Л принадлежит Р' тогда и только тогда, когда в множестве правил Р грамматики С есть правило Я -+ Л, а для конечного автомата М имеет место ае е Р; В.б. Алгебраические свойства КС-хлынов 669 2) для любого правила А †« у в Р (у ~ Л) в Р' вводится множество всех правил вида [з1Аза+1] -«[в1 у(1)зг][вг у(2)вз]...
[вау()с)за+1] ДЛЯ ПРОИЗВОЛЬНОЙ ПОСЛЕДОВатЕЛЬНОСтИ В1, Вг, ..., В«+1 СОСтОЯНИй из множества Я (Й > 1 — длина цепочки у); 3) для любого заключительного состояния ду Е Р конечного автомата М в Р' вводится правило вывода У -+ [дОЯду], где Я— аксиома грамматики С; 4) правило вывода [дат] -+ а для а Е У принадлежит Р' тогда и только тогда, когда команда да ~ г принадлежит системе команд б конечного автомата М; 5) никаких других правил вывода, кроме указанных в пп. 1- 4, множество Р' не содержит. Непосредственно из построения грамматики С' видно, что пустая цепочка Л порождается грамматикой 0' тогда и только тогда, когда правило вывода Я -«Л содержится в множестве Р, т.е.
Л Е Ь, и конечный автомат М допускает пустую цепочку, т.е. до Е Г. Итак, У)-' Л тогда и только тогда, когда Л Е ЬПВ. Для непустой цепочки х = х(1)х(2)... х(т) можно доказать (подробное доказательство мы опускаем'), что Я «-~ х, т.е. х Е Ь,тогда и только тогда, когда а ) [додд/] ) " [дох(1)з1][з1х(2)вг]... [зю — 1х(т)д/] для любых з1, ...,вю 1 Е Я.
Тогда из цепочки [дох(1)в1ив1х(2)вг]... [вю 1х(т)ду] цепочка х = х(1)х(2)... х(т) может быть выведена в грамматике 0' применением правила, приведенного вьппе в п. 4, в том и только в том случае, когда для конечного автомата М имеет место до — «х11) В1 «х(г) Вг -+ ... — «Зт-1 ~х(в«) дУ *Это доказательство беэ особого труда может быть восстановлено с помощью метода индунпии по длине вывода. 670 8. КОНТЕКСТНО- СВОБОДНЫЕ ЯЗЫКИ для некоторых состояний вм ..., з„, и т.е.
х читается на пути из до в ду, проходящем через состояния зм ..., з„, и и тем самым х б В, т.е. я Е г П В. Итак, окончательно я е Ь(С') е~ я е Ь П В. ~ Пример 8.21. Построим грамматику, порождающую пересечение языка всех палиндромов в алфавите [а,Ь) с языком а'ЬЬа". Грамматику для языка палиндромов задаем в виде о'-+ аТа]ЬТЬ[аа[ЬЬ]а]Ь[Л, Т-+ аТа] ЬТЬ[аа[ЬЬ[а[Ь, где о' — аксиома. Граф конечного автомата, допускающего язык а*ЬЬа*, приведен на рис. 8.36.
а а Согласно правилам построения грам- Ь Ь матики С', изложенным в доказательстве теоремы 8.11, имеем следующую граммаРис. З.зе тику для пересечения заданных языков: У вЂ” Ф Ыоо'а], [г1$г4] -~ [г1агг][ггТтз][гзат4] [[г1Ьгг][ггТгз][гзЬгз] (8.20) (для любых последовательностей состояний гм гг, гз, тз конеч- ного автомата); [гФгз] -+ [г1агг][г1огг] [[г1Ьгг][ггЬгз] (для любых последовательностей состояний гм гг, гз конечного автомата); [г1 Бгг] -+ [г~ агг] ] [г1 Ьгг] (для любых последовательностей состояний гм гг конечного автомата); [г1Тг4] ~ [г1огг] [ггТгз][гзаг4] ] [г1 Ьгг] [ггТгз] [гзЬг4] 8.о. Ааге61еавчесвне свойства КСвэывов 671 (для любых последовательностей состояний г1, г2, гз, г4 конеч- ного автомата); [г1Тгз] -+ [г1агг][г1агг] ][г1Ьг2][ггЬгз] (8.21) (для любых последовательностей состояний г1, г2, гз конечного автомата); [г1 Тгз] -+ [г1аг2И [г1 Ьго] (для любых последовательностей состояний г1, г2 конечного автомата); Рассмотрим пример порождения какой-нибудь цепочки вз определенного вьппе пересечения двух языков.
Возьмем цепочку аЬЬа. Выведем сначала „двойника" Отой цепочки, в котором каждый символ „окружен" состояниями конечного автомата. В процессе вывода мы стараемся „положить" нашу цепочку на некоторый путь из начальной вершины автомата в заключительную: о с ~чооч2] с ~чо<чОЪчотч2][ч2ач2] с [?опало][чоьд1][ч1ЬЯ2][Я2~н2] На втором шаге написанного вьппе вывода мы применили первое из правил (8.20) при г1 = г2 = оо, гз = г4 = О2, а на третьем шаге — второе правило (8.21) при г1 = 6о, г2 = й гз = Ф. Теперь мы видим, что все „скобки" состояний можно еотряхнуть": последовательно применяя правила (8.22)-(8.25), получаем цепочку аЬЬа.
Рассмотрим теперь „неправильную" цепочку аЬа ф а*ЬЬа". Вывод ее „двойника" может быть таким: У'1 ЫОБЯг] 1 Жоао][6ОТЧЙФа62] ~ [чоас1ОЪ3оЬЯ2][ч2ач2]. [боево] -+ а, [доЬ21] -+ Ь~ [61Ь62] -+ Ь, [42ад2] -~ а. (8.22) (8.23) (8.24) (8.25) 672 в. контнкстно-сноноднын языки При выводе мы старались помещать каждый входной символ конечного автомата между такими состояниями, чтобы он входил в метку дуги иэ первого во второе состояние, но мы видим, что нетерминал ~деЬдэ] не может быть заменен ни одним терминалом, и вывод зашел в тупик. Разбор других вариантов вывода „двойника" цепочки аЬа мы опускаем. В данном случае оказывается, что любой вывод закончится тупиковой цепочкой.;К Заметим, что в рассмотренном примере конструкцию теоремы нельзя применять к грамматике языка палиндромов, если она задана в виде Я ~ аЯа~ЬЯЬ)а~ 6~Л, поскольку в этом случае нельзя обойтись без применения правила Я -~ Л при порождении цепочки четной длины. Так как при построении грамматики С' правила с пустой правой частью (иэ множества правил грамматики С) никак не преобразуются, грамматика 6' в таком случае не породит „двойника" ни одной цепочки четной длины языка палиндромов.
Следовательно, требование, чтобы грамматика КС-языка Ь была задана в приведенной форме и ее единственное разрешенное Л-правило Я-+ Л применялось только при выводе пустой цепочки, является существенным при построении КС-грамматики для пересечения языка Ь с регулярным языком и. Доказанное утверждение о „контекстной свободности" пересечения КС-языка с любым регулярным языком в совокупности с леммой о разрастании для КС-языков полезно при доказательстве утверждений о том, что какой-либо язык не является контекстно-свободным. Пример 8.22.
Докажем, что язык Ь = (пил: ю Е (а,6~')— так называемый язык двойных слов в алфавите (а, 6) — не является контекстно-свободным. д.а1. О методах еиитаатичееиого аиализа КС-лзыиоа 673 Применить к решению этой задачи сразу лемму о разрастании довольно трудно. Поступим так. Рассмотрим пересечение языка Ь с регулярным языком а*Ь"а'Ь'. Легко понять, что это пересечение состоит из всех цепочек вида а"'ЬиаитЬ" (т, п > 0). Предполагая, что язык Ь контекстно-свободный, получим в силу теоремы 8.11, что контекстно-свободным является и язык 1атпЬ"атаЬ": т,п > О). Однако этот язык не есть КС-язык (см. пример 8.12).
Следовательно, не является КС-языком и исходный язык й. Дополнение 8.1. О методах синтаксического анализа КС-языков Проблема синтпаксического анализа для КС-языков состоит в построении алгоритма, который по любой КС-грамматике С = (т, Ф, Я, Р) и цепочке х в ее терминальном алфавите У распознает, принадлежит ли х языку Ь(С), порождаемому грамматикот1 С. В случае положительного ответа на вопрос алгоритм должен строить дерево вывода х в грамматике С. Существование такого алгоритма следует из факта разрешимости проблемы принадлезхности для КС-языков. Мы рассмотрим некоторые алгоритмы синтаксического анализа для определенных классов КС-язьпсов.
Прототипом синтаксического анализатора является МП-автомат, который строится по данной КС-грамматике (см. 8.4), но такой МП-автомат, как мы видели, являетсл в общем случае недетерминированным и может даже для допустимот1 цепочки построить вывод, который заканчивается тупиковой конфигурациеб. Чтобы на основе такого распознаватпеля построить алгоритм синтаксического анализа (и тем самым превратить распознаватель в анализатпор), нужно разработать определенный механизм управления выводом на множестве конфигураций МП-автоматпа. Этот механизм должен обеспечить эффективный поиск допускатотцеб последовательностпи конфи- 674 г. кОнтекстнО-сВОБОдные языки гураиий для допустимых цепочек.
В частности, может быть поставлена задача разработки алгоритма бесгпупикового, или однопроходного, анализа. Беступиковый анализ имеет место, если получение тупиковой конфигурации в процессе анализа означает „неправильность" анализируемой цепочки, т.е. тот факт, что она не принадлежит языку, порождаемому заданной грамматикой.
Беступиковый анализ, как можно показать, невозможен в случае произвольного КС-языка, но для некоторых (достаточно широких) классов КС-языков он может быть реализован. Некоторые алгоритмы беступикового синтаксического анализа мы очень коротко рассмотрим в этом дополнении. Существуют две основные стратегии синтаксического анализа: 1) нисходяиаий анализ (называемый также англизом „сверху вниз", или анализом „развергпкой") и 2) восходящий анализ (анализ „снизу вверх", „свергпкой").
В нисходящем анализе дерево вывода цепочки строится от корня к яисшьям, т.е. дерево вывода „реконструируется" в прямом порядке, и аксиома граммашики „развертывается" в цепочку. В восходящем анализе дерево вывода строится от листьев к корню и анализируемая цепочка „свертывается" в аксиому. Рассмотрим две стратегии анализа по очереди. Нисходящий анализ. ЬЬ(к)-грамматики. Мы видели, что МП-автомат, который при доказательстве теоремы 8.8 мы строили по данной КС-грамматике, „воспроизводит" левый вывод в грамматике.
Основнгл „задача" данного автомата как распознавателя состоит в том, чтобы на каждом шаге „угадать" очередное применяемое правило вывода и „правильно выбрать" соответствующую команду при построении допускающей последовательности конфигураций. Механизм управления выводом, которым мы должны снабдить классический МП- автомат, должен обеспечить выбор команды (единственной в случае беступикового анализа) по определенной информации о состоянии процесса поиска дерева вывода (или, что равно- Д.8.Ь О иетодак сявтаксятескосо аяакаэа КСкаикоа 675 сильно, левого вывода) входной цепочки. Обычно механизм управления выводом реализуется в виде специальных таблиц, которые называют управллюи4ими шаблицами и которые можно рассматривать как дополнительное устройство памяти в МП-автомате. Существует класс грамматик, называемых Ы(ус)-грамматиками, в которых применяемая команда однозначно определяется: 1) нрочитпанной часшью ~о входной цепочки; эту цепочку 1о называют левым контпекстпом; 2) находящимся в данный момент в верхней лчеаке магазина нешерминальным символом А; 3) началом (пре$иксом) о непрочитанной часпьи цепочки, состоящим не более чем из к букв (к > 1); этот префикс называют авакцепочкоб (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
