XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 81
Текст из файла (страница 81)
Теорема Клввя 509 быть бесконечным (каждый путь имеет конечную длину, но множество всех таких путей может оказаться бесконечным, содержать пути сколь угодно большой длины — простейший пример дает петля, по которой можно пройти сколько угодно раз). Поэтому объединение при определении стоимости прохождения между парой состояний конечного автомата мы можем сейчас рассматривать только как операцию замкнутого полукольца всех языков в данном алфавите, а именно опера цию вычисления точной верхней грани („ бесконечная сумма" в замкнутом полукольце). Но коль скоро элементы матрицы стоимостей уже вычислены, их объединение (в формуле (7.5)), дающее язык конечного автомата, разумеется, конечно. Позже будет доказано, что на самом деле все стоимости в конечном автомате также регулярны.
О языке Ь(М) говорят, что он допускается (или воспринимается) конечным автоматом М. О любой цепочке, принадлежащей языку Ь(М), говорят, что она допускается (или воспринимается) конечным автоматом М. Такую цепочку называют также допустпимой цепочкой данного конечного аепаомаепи.
Определение 7.10. Два конечных автомата М~ и Мз называют зквиепаентпными, если их языки совпадают: ЦМ~) = ЦМз). Установим теперь связь между понятиями конечного автомата и регулярной грамматики. Теорема 7.б. Язык допускается конечным автоматом тогда и только тогда, когда он порождается регулярной грамматикой. ч Чтобы доказать теорему, нужно: 1) указать способ построения регулярной грамматики 6 по заданому конечному автомату М, такой, чтобы яэмк, по- 510 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ рождаемый грамматикой С, совпадал с языка, допускаемым автоматом М: Ь(С) = ЦМ); 2) указать способ построения конечного автомата М по заданной регулярной грамматике С, такой, чтобы язык, допускаемый автоматом М, совпадал с языком, порождаемьпе грамматикой С: Ь(М) = Ь(С). Замечание 7.9.
Регулярную грамматику С и конечный автомат М, такие, что Ь(С) = Ь(М), иногда называют эквивалентными. Рассмотрим зти построения по очереди. 1. Построение регулярной грамматики по конечному автомату. Пусть дан конечный автомат М = (У, 1д, ов,,Р, б) Определим регулярную грамматику С = (У, Ф, о', Р) следующим образом: терминальный алфавит У совпадает с входным алфавитом автомата М; нетерминальный алфавит Ф находится во взаимно однозначном соответствии с множеством состояний Я автомата М, причем состоянию о е Я сопоставлен нетерминал Яв Е Ф и аксиома сопоставлена начальному состоянию ов, т.е. з = о „множество правил вывода Р строится по системе команд б так: пРавило вывода зв -+ ао„где а Е У 0 (Л1, принадлежит Р тогда и только тогда, когда в д есть команда оа -+ г; кроме того, если (и только если) состояние г заключительное (г й Р), то в Р добавляется правило вывода Яв -+ а.
Если же оо б Р (и только в этом случае), то в Р помещаем правило вывода Явь — ь Л. Для конечного автомата на рис. 7.5 получим следующую регулярную грамматику: Явь -+ Ось ~ 1Яць ! ОЯв„ Бч1 Ф ОЯФ2! 0$ Яв, -+ ОЯц, ~ 1Яв, ~ 0 ! 1. У.о. Калечные автоматы.
Теорема Коими 511 Заметим, что, читая цепочку в автомате, в грамматике мы ее выводим (порождаем). Например, до -+о щ -+о дз -+1 дз и Яее 1-ОЯ„~-ООЯ„1- 001. Докажем, что описанное построение корректно, т.е. ЦС) = = Ь(М). Для этого сначала, используя индукцию по длине и пути в конечном автомате М, докажем, что иэ факта достиихсиаеости д ~" т в автомате М (для любого п > 0) следует емоодиаеость Яа 1-й хЯ„в грамматике 6' для любых д,т Е Я и х Е У'. Пусть длина пути п = О, т.е. д ~~~ т и т = д. Так как метка пути нулевой длины в ориентированном графе, размеченном над полукольцом К(У), равна единице полукольца — регулярному выражению Л, то д ~ел д при х = Л. Но Яа 1-п~ Яа выполняется тривиально. Пусть для любого и < тп — 1 из достижимости д =ь~~ т следует выводимость Я» 1-' хЯ;, и пусть в автомате М существует путь тт' длины тп, ведущий из вершины д в вершину т, на котором читается цепочка х, т.е.
д ~'" т. Так как длина пути тт' не меньше 1, то в нем есть по крайней мере одна дуга и существуют такая вершина д' и такое а Е У 01Л), что д-+„д' =Ь'„" 1 т, где ау = х (мы выделили первую дугу пути ет'). Тогда, согласно построению множества Р правил вывода грамматики С, в Р содержится правило Яа -+ аЯа, а, по предположению индукции, из того, что в М д' =ь'„" 1 т, следует, что Яа 1-йуЯ„.
В итоге получаем Яя1-аале ~-йауЯ, =хЯ„т.е. ое 1-й хЯ„, что и требовалось. Теперь если цепочка х Е Ь(М), то в М существует путь, ведущий из начального состояния до в одно иэ заключительных состояний ду, на котором читается цепочка х, т.е. де ~' ду для некоторого дуб Р. Если ду =до и тогда х= Ле Ь(М), то в множестве Р правил вывода есть правило Яее -+ Л и Л е ЦС). Если же ду отлично от дс, то, какова бы ни была цепочка х, путь иэ дс в ду, на котором она читается, имеет длину, не меньшую единицы.
Выделяя в этом пути последнюю дугу, получим де =ь„' д' -+, ду, где уа = х. Но тогда, во-первых, 512 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ как мы только что доказали, в грамматике С имеет место выводимость Неь ~-О уНе, а, во-вторых, из того, что д'-+ оу, согласно построению множества правил вывода грамматики С, следует, что в ней есть правило Н -+ а, и окончательно получим Нева-ОуН 1-уа=х, т.е. х Е ЦС). Таким образом, мы полностью доказали, что для каждой цепочки х Е У' из того, что х Е ЦМ), следует х Е ЦС), т.е.
имеет место включение ЦМ) С Ь(С). Чтобы доказать обратное включение, используя индукцию по длине и вывода в грамматике С, покажем сначала, что из факта выводимости Не 1-н~ хН; (длл любого н > 0) следует достижимость о =о*. г в автомате М для любых о, г Е Я и х Е У'. При и = 0 имеем Не Я Нв, х = Л и тривиально выполняется Ч~лЧ. Пусть для любого й ( ш — 1 из выводимости Яе ~~~ хЯ, следует достижимость д =ь' г (в автомате М), и пусть в грамматике С существует вывод Ю длины га цепочки хН,. из цепочки Не, т.е. Не 1-~~ хН Так как длина вывода Ю не меньше 1, то найдетсЯ такой нетеРминал Не~ и такое а Е У01Л), что Не 1-о аНв ~-~~ ауЩ где ау = х (мы выделили первый шаг вывода Ю). Непосредстпвеннал выводимость Не 1-а аНв означает, что в множестве правил вывода грамматики С содержится правило Нв -+ аЯ и, следовательно, в системе команд б конечного автомата М есть команда да ~ о' и тогда о ~„д'.
Согласно предположению индукции, из того, что о' Я 1 уН,, следует, что д'=ь',т в М. В итоге получаем о ~ь д' ~,', г, т.е., так как ау =х, д=ь' г, что и требовалось. Если теперь х Е ЦС), то в грамматике С существует вывод цепочки х из аксиомы Неь, т.е. Не, 1-а х. На последнем шаге этого вывода применяется некоторое правило, правая часть которого не содержит вхохеденнй нетерминалов, т.е. правило вида Н -+ а. Поскольку любвл цепочка в выводе в регулярной 7.0. Ковечаые автоматы. Теорема Камеи 513 грамматике может содержать нетерминзл только как последний символ, то Я,в ~-й уЯ 1-ода= х. Отсюда следует, что ае =~„' д'.
Кроме того, правило вывода Я -~ а может принадлежать множеству Р тогда и только тогда (по построению Р), когда в системе команд автомата М есть команда д'а -+ ду, ду Е Г. Следовательно, де ~„' 1у' -+о ау, что и означает де =~' ду, т.е. х Е ЦМ). Итак, доказано включение ЦС) С ЦМ), и 1 (С) = ЦМ), т.е. регулярная грамматика С, построенная, как описано выше, по конечному автомату М, эквивалентна ему. 2, Построение конечного автомата но регулярной грамматике.
Но заданной регулярной грамматике С=(У, уе, Я, Р) построим конечный автомат М = ( е', Я, де, Р, б) так, что входной алфавит автомата М совпадает с терминальным алфавитом грамматики С, множество состояний Я совпадает с нетерминальным алфавитом грамматики С, пополненным новым состоянием у, не принадлежащим объединенному алфавиту грамматики С, т.е. Я = Ж О (у'); начальное состояние де совпадает с аксиомой Я, множество заключительных состояний Р = Щ.
Система команд б определяется следующим образом: команда Аа ~ В принадлежит б тогда и только тогда, когда в множестве Р правил вывода есть правило А ~ аВ, а команда Аа -+ у принадлежит б тогда и только тогда, когда правило вывода А ~ а принадлежит множеству Р. Например, по регулярной грамматике Се из примера 7.5 строится конечный автомат с входным алфавитом (а, Ь, О, Ц, множеством состояний (1,Р,у), начальным состоянием 1, единственным заключительным состоянием у и такой системой команд (рис. 7.6): 1а-+Р, 1Ь-~Р, Ра-+Р, РЬ-1 Р, РО-тР, Р1-тР, Ра — 1 у', РЬОУ', РО-+~, Р1-+У', 1а-+~, ХЬ-+~. 1Π— 10061 514 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
