Допустимость языка конечным автоматом
О языке говорят, что он допускается (или воспринимается) конечным автоматом . О любой цепочке, принадлежащей языку , говорят, что она допускается (или воспринимается) конечным автоматом . Такую цепочку называют также допустимой цепочкой данного конечного автомата.
Определение 7.10. Два конечных автомата и называют эквивалентными, если их языки совпадают:
Установим теперь связь между понятиями конечного автомата и регулярной грамматики.
Теорема 7.5. Язык допускается конечным автоматом тогда и только тогда, когда он порождается регулярной грамматикой.
Чтобы доказать теорему, нужно:
1) указать способ построения регулярной грамматики по заданному конечному автомату , такой, чтобы язык, порождаемый грамматикой , совпадал с языком, допускаемым автоматом ; 2) указать способ построения конечного автомата по заданной регулярной грамматике , такой, чтобы язык, допускаемый автоматом , совпадал с языком, порождаемым грамматикой .
Замечание 7.9. Регулярную грамматику и конечный автомат , такие, что , иногда называют эквивалентными.
Рассмотрим эти построения по очереди.
Построение регулярной грамматики по конечному автомату
Пусть дан конечный автомат
Определим регулярную грамматику следующим образом: терминальный алфавит совпадает с входным алфавитом автомата ; нетерминальный алфавит находится во взаимно однозначном соответствии с множеством состояний автомата , причем состоянию сопоставлен нетерминал и аксиома сопоставлена начальному состоянию , то есть ; множество правил вывода строится по системе команд так: правило вывода , где , принадлежит тогда и только тогда, когда в есть команда ; кроме того, если (и только если) состояние заключительное , то в добавляется правило вывода . Если же (и только в этом случае), то в помещаем правило вывода .
Для конечного автомата на рис. 7.5 получим следующую регулярную грамматику:
Заметим, что, читая цепочку в автомате, в грамматике мы ее выводим (порождаем). Например,
 и  .
Докажем, что описанное построение корректно, т.е. . Для этого сначала, используя индукцию по длине пути в конечном автомате , докажем, что из факта достижимости в автомате (для любого ) следует выводимость в грамматике для любых и .
Пусть длина пути , то есть и . Так как метка пути нулевой длины в ориентированном графе, размеченном над полукольцом , равна единице полукольца — регулярному выражению , то при . Но выполняется тривиально.
Пусть для любого из достижимости следует выводимость , и пусть в автомате существует путь длины , ведущий из вершины в вершину , на котором читается цепочка , то есть . Так как длина пути не меньше 1, то в нем есть по крайней мере одна дуга и существуют такая вершина и такое , что , где (мы выделили первую дугу пути ). Тогда, согласно построению множества правил вывода грамматики , в содержится правило , а, по предположению индукции, из того, что в имеется , следует, что . В итоге получаем , то есть , что и требовалось.
Теперь если цепочка , то в существует путь, ведущий из начального состояния в одно из заключительных состояний , на котором читается цепочка , то есть некоторого . Если и тогда , то в множестве правил вывода есть правило и . Если же отлично от , то, какова бы ни была цепочка , путь из в , на котором она читается, имеет длину, не меньшую единицы. Выделяя в этом пути последнюю дугу, получим , где . Но тогда, во-первых, как мы только что доказали, в грамматике имеет место выводимость , а, во-вторых, из того, что , согласно построению множества правил вывода грамматики , следует, что в ней есть правило , и окончательно получим
 , то есть  .
Таким образом, мы полностью доказали, что для каждой цепочки из того, что , следует , т.е. имеет место включение .
Чтобы доказать обратное включение, используя индукцию по длине вывода в грамматике , покажем сначала, что из факта выводимости (для любого ) следует достижимость в автомате для любых и .
При имеем и тривиально выполняется .
Пусть для любого из выводимости следует достижимость (в автомате ), и пусть в грамматике существует вывод длины цепочки из цепочки , то есть . Так как длина вывода не меньше 1, то найдется такой нетерминал и такое , что , где (мы выделили первый шаг вывода ). Непосредственная выводимость означает, что в множестве правил вывода грамматики содержится правило и, следовательно, в системе команд конечного автомата есть команда и тогда . Согласно предположению индукции, из того, что , следует, что в . В итоге получаем , т.е., так как , что и требовалось.
Если теперь , то в грамматике существует вывод цепочки из аксиомы , то есть . На последнем шаге этого вывода применяется некоторое правило, правая часть которого не содержит вхождений нетерминалов, т.е. правило вида . Поскольку любая цепочка в выводе в регулярной грамматике может содержать нетерминал только как последний символ, то . Отсюда следует, что . Кроме того, правило вывода может принадлежать множеству тогда и только тогда (по построению ), когда в системе команд автомата есть команда . Следовательно, , что и означает , то есть .
Итак, доказано включение , и , т.е. регулярная грамматика , построенная, как описано выше, по конечному автомату , эквивалентна ему.
Построение конечного автомата по регулярной грамматике
По заданной регулярной грамматике
построим конечный автомат так, что входной алфавит автомата совпадает с терминальным алфавитом грамматики , множество состояний совпадает с нетерминальным алфавитом грамматики , пополненным новым состоянием , не принадлежащим объединенному алфавиту грамматики , то есть ; начальное состояние совпадает с аксиомой , множество заключительных состояний }. Система команд определяется следующим образом: команда принадлежит тогда и только тогда, когда в множестве правил вывода есть правило , а команда принадлежит тогда и только тогда, когда правило вывода принадлежит множеству .
Например, по регулярной грамматике из примера 7.5 строится конечный автомат с входным алфавитом , множеством состояний , начальным состоянием , единственным заключительным состоянием и такой системой команд (рис. 7.6):
Обоснование корректности этого построения может быть проведено так же, как и построения регулярной грамматики по конечному автомату ("двойной" индукцией по длине вывода в грамматике и по длине пути в автомате), и мы его опускаем.
Таким образом, конечные автоматы допускают в точности те же языки, которые порождают регулярные грамматики.
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|