XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 100
Текст из файла (страница 100)
в.4. Магааинвые автоматы В частности, при и = 0 получаем, что любая конфигурация выводится сама иэ себя; при и = 1 получаем непосредственную выводимость С' из С. В общем случае говорят, что конфигурация С' выводится из конфигурации С за и шагов, записывая при этом С 1-" С'. Желал подчеркнуть, что существует вывод ненулевой длины конфигурации С' из конфвгурации С, т.е. С 1-" С' и и > О, записывают С 1-+ С'. Таким образом, понятие выводимости для конфигураций МП-автомата вводится аналогично таковому для грамматики.
И к тому же сохраняется полная аналогия с понятием дос~иижимости в ориентиврованнмх гра4ах. В терминах конфигураций может быть дано и строгое определение языка МП-автомата. Определение 8.10. Входную цепочку х называют допустимой цепочкой МП-автомата М (см. определение 8.7), если на множестве конфигураций М существует вывод, связывающий начальную конфигурацию (дг,х,ле) с заключительной конфигурацией (ду, Л, Л), где еу Е Р, т.е. Язык, допускаемый МП-автоматом М (или просто язык МП- автомата М), — это множество всех его допустимых цепочек. МП-автоматы М~ и Мэ называют экенеалентиныкн, если их языки совпадают, т.е. ЦМ~) = ЦМэ).
Любой вывод на множестве конфигураций МП-автомата, связывающий начальную конфигурацию Се — — (де,х,Яе) с одной из заключительных, называют допускающей иоследоеатиелъностиью конфигураций длл цепочки х. Цепочка х принадлежит языку ЦМ) тогда и только тойда„когда для нее существует допускающая последовательность конфигураций. Тем не менее может оказаться так, что даже в том случае, когда х е Ь(М), из начальной конфигурации Се можно вывести отнюдь не только заключительную конфигурацию. 838 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Мо = ((до,д1,дг), (а,6), (Я, а,ь), 9о,(дз), Я, Ьз) Можно доказать, что этот МП-автомат допускает зеркальный язык 1хх~ Е (а, Ь) ), где х обозначает инверсию ивиочии х.
Приведем допускающую последовательность конфигураций для цепочки аььа: (до аььа ~) ~ (ц (9о ЬЬа а~) Г (о) (9о Ь~~ Ьа~) ~ (о1 ~<,> (9„а, аг) 1-<„(д„Л, г) 1-Оц (9„Л, Л) (справа внизу под значками непосредственной выводимости подписаны номера применяемых команд). К начальной конфигурации (до, а66а, Я) применима только команда (1). После выполнения этой команды первый символ входной цепочки будет прочитан, а в магазине вместо одного символа Я окажется цепочка аЯ, т.е. символ а станет верхним символом магазина. К полученной конфигурации (до, Ььа, аЯ) применима только команда (б), в результате выполнения которой будет прочитан еще один символ входной цепочки, т.е.
ее второй символ 6, и в магазине окажется цепочка ЬаЕ. Пример 8.15. Пусть МП-автомат опРеДелен множеством команД бьс1 дову -+ доаЕ, 9оЫ -+ 9оЫ, 9оаа -+ 9оаа, чоаа -+ 91Л, 9оаь -+ доаь, 906а — > ЧОЬа, доЬЬ -+ 9оЬЬ, доьь-+ д1Л 91аа -+ 91Л, 9166- 91Л, 91ЛЯ- 9,Л.
(1) (2) (3) (4) (5) (б) (7) (8) (9) (10) (11) 637 8.4. Магаэявяые автоматм К третьей конфигурации записанного вьппе вывода применимы две команды: (7) и (8). Выбирая команду (8), мы тем самым читаем третий символ входной цепочки, а верхний символ магазина, совпавший с указанным символом входной цепочки, „выталкиваем" иэ магазина, после чего верхним символом магазина окажется уже символ а, т.е. возникнет конфигурация (9м а, аЯ). Заметим также, что после выполнения команды (8) МП-автомат Мг окажется в новом состоянии дь Применив к конфигурации (9м а, аЯ) единственную применимую к ней команду (9), получим конфигурацию (д~, Л, 2), т.е.
входная цепочка прочитана полностью, а в магазине остался символ Я. Применяя опять-таки единственно возможную для такой конфигурацию команду (11), мы убираем символ Я иэ магазина, тем самым опустошая его, и переходим в заключительное состонние 9э. В то же время, если бы после третьей конфигурации было выбрано „неудачное продолжение", т.е. была бы применена команда (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. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Отсюда в силу (8.13), будем иметь (д, ах'у», Еа7) ~ (д', »у», оа'7) ~-и (г у», о7)~ т.е. при выводимости (8.10) за и шагов имеет место и выводимость (8.11) также за и шагов, что и требовалось доказать. Аналогично (но уже индукцией по длине вывода (8.11)) доказывается, что если имеет место выводимость (8.11), то имеет место и выводимость (8.10). ~ МП-автомат М называют эниваленпзнььи КС-граммон»ине С, если язык, допускаемый М, совпадает с языком, порождаемым грамматпиноа С, т.е. если й(М) = Ь(С).
Опишем алгоритм построения по заданной КС-грамматике эквивалентного ей МП-автомата, а также алгоритм построения по заданному МП-автомату КС-грамматики, которой он эквивалентен. Алгоритм построения МП-автомата по КС-грамматике. Для исходной КС-грамматики С = (У, Ф, о', Р) определим МП-автомат Мс = ((д), К У ОЖ, д, (д), Я, б) (с единственным состоянием о), система команд б которого строится следующим образом: для каждого правила А -+ а, принадлежащего Р, в б записывается команда оАА -+ да и для каждого а Е У вЂ” команда даа -+ оЛ.
Никаких других команд в системе команд б нет. Пример 8.16. Пусть дана грамматика С=((а, Ь,с), (о), о, Р), множество правил вывода Р которой есть о'-+ об'ЬЯ)аЯ)с. 8.4. Магазиввые автоматы Тогда эквивалентный ей МП-автомат задается следующей системой команд: дЛЯ ~ даЯЬБ~даЯ~ дс, даа -+ дЛ, д6Ь -+ дЛ, дсс-> дЛ (мы использовали сокращенную запись нескольких команд с одинаковыми левыми частями по аналогии с тем, как мы это делаем при записи множества правил вывода грамматики). В системе команд МП-автомата, который строится по заданной КС-грамматике так, как это описано вьппе, мы видим два „сорта" команд: 1) команды, „моделирующие" применение правил, исходной грамматики (в данном примере это команды первой строки); при выполнении каждой такой команды МП- автомат делает Л-такт, т.е.
не продвигает головку по входной ленте; 2) команды „сравнения", согласно которым МП-автомат должен убирать верхний символ магазина всякий раз, когда он совпадает с обозреваемым символом на ленте. Тогда, читая входную цепочку, такой МП-автомат „моделирует" левый вывод этой цепочки в исходной грамматике, применяя каждый раз, когда верхним символом магазина оказывается нетерминзл, команду „первого сорта" и всякий раз, когда верхним символом магазина оказывается терминал исходной грамматики, „команду сравнения".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
