Конечные автоматы и А-грамматики

Установим теперь соответствие между А-грамматиками и конечными автоматами. Грамматика G = (N, T, P, S) и автомат A = (Q, T, t, q ₀, F) называются соответствующими друг другу, если N = Q, S = q ₀, X ® aY Î P Û (X, a) ® Y Î t, X ® e Î P Û X Î F.

Для того, чтобы доказать, что в этом случае L (G) = L (A), введем понятие диаграммы А-грамматики. Это помеченный ориентированный граф, вершинами которого являются символы из N, помеченная дуга X - a ® Y соответствует правилу X ® aY. Если X ® e Î P, то вершину X будем изображать двойным кружком.

Пример 4.2. Построенная в примере 3.11 А-грамматика для чисел представляется диаграммой



Очевидны также следующие леммы.

Л е м м а 4.2. X ® _G ^* aY Û в диаграмме грамматики есть путь из X в Y, метки дуг которого образуют цепочку a.


Л е м м а 4.3. Графы соответствующих друг другу грамматики и автомата совпадают.


Из лемм 4.1-4.3 непосредственно следует

Т е о р е м а 4.1. L (G) = L (A) для соответствующих друг другу грамматики G и автомата A.


Заметим, что автомат, соответствующий грамматике чисел, является детерминированным. Но не всегда легко записать детерминированный автомат для сложного регулярного языка. В следующем разделе рассматривается способ построения наиболее эффективного детерминированного автомата для произвольного регулярного языка. Это построение может осуществляться автоматически.

С л е д с т в и е 4.1. Класс регулярных языков совпадает с классом языков, допускаемых конечными автоматами.


Дата добавления: 2014-01-07