Теория и реализация языков программирования



Связь регулярных множеств, конечных автоматов и регулярных грамматик - часть 2


(1) каждое ее правило, кроме S

e, имеет вид либо A
aB, либо A
a, где
A, B \in N, a \in T,

(2) в том случае, когда

S \rightarrow e \in P
, начальный символ S не встречается в правых частях правил.

Лемма. Пусть G - праволинейная грамматика. Существует регулярная грамматика G' такая, что L(G) = L(G').

Доказательство. Предоставляется читателю в качестве упражнения.

Теорема 3.2. Пусть G = (N, T, P, S) - праволинейная грамматика. Тогда существует конечный автомат M = (Q, T, D, q0, F) для которого L(M) = L(G).

Доказательство. На основании приведенной выше леммы, без ограничения общности можно считать, что G - регулярная грамматика.

Построим НКА M следующим образом:

  1. состояниями M будут нетерминалы G плюс новое состояние R, не принадлежащее N. Так что
    Q = N \cup \{R\}
    ,
  2. в качестве начального состояния M примем S, то есть q0 = S,
  3. если P содержит правило S
    e, то
    F = {S, R}
    , иначе F = {R}. Напомним, что S не встречается в правых частях правил, если
    S \rightarrow e \in P
    ,
  4. состояние
    R \in D(A, a)
    , если
    A \rightarrow a \in P
    . Кроме того, D(A, a) содержит все B такие, что
    A \rightarrow aB \in P. \; \; D(R, a) = \oslash
    , для каждого
    a \in T
    .

M, читая вход w, моделирует вывод w в грамматике G. Покажем, что L(M) = L(G). Пусть

w = a_1a_2 \ldots a_n \in L(G), n > 1
. Тогда
S \Rightarrow a_1A_1 \Rightarrow \ldots \Rightarrow a_1a_2 \ldots a_{n-1}A_{n-1} \Rightarrow a_1a_2 \ldots a_{n-1}a_n
для некоторой последовательности нетерминалов A1, A2, ... , An-1. По определению, D(S, a1) содержит A1, D(A1, a2) содержит A2, и т.д., D(An-1, an) содержит R. Так что
w \in L(M)
, поскольку De(S, w) содержит R, а
R \in F
. Если
e \in L(G)
, то
S \in F
, так что e \in L(M).

Аналогично, если

w = a_1a_2 \ldots a_n \in L(M), \; n \geq 1
, то существует последовательность состояний S, A1, A2, ... , An-1, R такая, что D(S, a1) содержит A1, D(A1, a2) содержит A2, и т.д. Поэтому
S \Rightarrow a_1A_1 \Rightarrow a_1a_2A_2 \Rightarrow \ldots \Rightarrow a_1a_2 \ldots a_{n-1}A_{n-1} \Rightarrow a_1a_2 \ldots a_{n-1}a_n
- вывод в G и
x \in L(G)
. Если
e \in L(M)
, то
S \in F
, так что
S \rightarrow e \in P
и
e \in L(G)
.

Теорема 3.3. Для каждого конечного автомата M = (Q, T, D, q0, F) существует праволинейная грамматика G = (N, T, P, S) такая, что L(G) = L(M).

Доказательство. Без потери общности можно считать, что автомат M - детерминированный. Определим грамматику G следующим образом:

  1. нетерминалами грамматики G будут состояния автомата M. Так что N = Q,
  2. в качестве начального символа грамматики G примем q0, то есть S = q0,
  3. A \rightarrow aB \in P
    , если D(A, a) = B,
  4. A \rightarrow a \in P
    , если D(A, a) = B и
    B \in F
    ,
  5. S \rightarrow e \in P
    , если
    q_0 \in F
    .

Доказательство того, что

S \Rightarrow^* w
тогда и только тогда, когда
D^e(q_0, w) \in F
, аналогично доказательству теоремы 3.2.




Содержание  Назад  Вперед