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

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

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

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



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

Л е м м а  4.2. X _G^*Y     в диаграмме грамматики есть путь из X в Y, метки дуг которого образуют цепочку  . 

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

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

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

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

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

 

4.2. Детерминированные конечные автоматы

4.2.1. Детерминированные и недетерминированные автоматы

Автоматы A и A' называются эквивалентными, если L(A) = L(A').

Т е о р е м а   4.2. Для любого недетерминированного конечного автомата можно построить эквивалентный детерминированный конечный автомат.

Доказательство. Сначала заметим, что грамматика соответствует детерминированному автомату тогда и только тогда, когда в каждом ее правиле вида A  a₁A₁ | ... | a_nA_n или A  a₁A₁ | ... | a_nA_n |   выполняется условие: a_i  a_j при i  j. Поэтому достаточно преобразовать А-грамматику G = (N,T,P,S) к указанному виду. В процессе преобразования на грамматику будем смотреть, как на соответствующую систему уравнений.

Для каждого непустого подмножества {A₁,...,A_n} множества N введем новый нетерминальный символ [A₁,...,A_n] и определим его так, чтобы соответствующее уравнение имело вид [A₁,...,A_n] = A₁  ...  A_n. Для этого достаточно, как в доказательстве теоремы 3.10, задать правило [A₁,...,A_n]  r₁ | ... | r_n, где r_i  правая часть правила для A_i.

Теперь построим требуемую грамматику G' = (N',T,P',S), где N' получается из N добавлением определенных выше новых нетерминальных символов, а P' получено следующим образом из P и правил для новых нетерминальных символов: в каждом правиле все члены вида aA₁, ..., aA_n с одним и тем же a  T  заменяются одним членом a[A₁,...,A_n]. Таким правилам соответствует детерминированный автомат, эквивалентный исходному, т.к. a[A₁,...,A_n] = aA₁   ...  aA_n. 

Так как не все нетерминальные [A₁,...,A_n] достижимы из S, то при построении P' достаточно включать только необходимые правила, начиная с правила для S.

Пример 4.3. Недетерминированный автомат, изображенный на следующем рисунке слева,

имеет соответствующую грамматику с правилами

q₀  aq₁ | bq₂,  q₁  aq₁ | aq₃ | bq₁ | bq₂, q₂  aq₁ | aq₂ | bq₂ | bq₃,  q₃  aq₃ | bq₃ |  .

Преобразуем его в детерминированный автомат по методу теоремы 4.2. В новую грамматику войдет старое правило для q₀, т.к. оно удовлетворяет условию детерминированности. Правило для q₁ преобразуется к виду q₁  a(q₁ | q₃) | b(q₁ | q₂), или q₁  aq₁₃ | bq₁₂.

Аналогично получается правило для q₂:  q₂  aq₁₂ | bq₂₃.

Для q₁₃ = q₁ | q₃ правило имеет вид q₁₃  aq₁ | aq₃ | bq₁ | bq₂ | bq₃ |  , или, окончательно, q₁₃  aq₁₃ | bq₁₂₃ |  , где q₁₂₃ = q₁ | q₂ | q₃. Аналогично, для q₁₂ = q₁ | q₂, q₂₃ = q₂ | q₃ и q₁₂₃ правила (после преобразования) имеют вид q₁₂  aq₁₂₃ | bq₁₂₃, q₂₃  aq₁₂₃ | bq₂₃ |  , q₁₂₃  aq₁₂₃ | bq₁₂₃ |  .

Диаграмма построенного детерминированного автомата изображена на том же рисунке справа. 

Отметим, что, как видно из доказательства и примера, построенный детерминированный автомат при анализе цепочки как бы одновременно ведёт все пути её анализа исходным автоматом.