праволинейная грамматика. Существует регулярная грамматика

(1) каждое ее правило, кроме S e, имеет вид либо A aB, либо A a, где

(2) в том случае, когда , начальный символ 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. Так что
   
   ,
2. в качестве начального состояния M примем S, то есть q0 = S,
3. если P содержит правило S
   
   e, то
   
   , иначе F = {R}. Напомним, что S не встречается в правых частях правил, если
   
   ,
4. состояние
   
   , если
   
   . Кроме того, D(A, a) содержит все B такие, что
   
   , для каждого
   
   .

M, читая вход w, моделирует вывод w в грамматике G. Покажем, что L(M) = L(G). Пусть . Тогда для некоторой последовательности нетерминалов A1, A2, ... , An-1. По определению, D(S, a1) содержит A1, D(A1, a2) содержит A2, и т.д., D(An-1, an) содержит R. Так что , поскольку De(S, w) содержит R, а . Если , то , так что e \in L(M).

Аналогично, если , то существует последовательность состояний S, A1, A2, ... , An-1, R такая, что D(S, a1) содержит A1, D(A1, a2) содержит A2, и т.д. Поэтому - вывод в 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. 
   , если D(A, a) = B,
4. 
   , если D(A, a) = B и
   
   ,
5. 
   , если
   
   .

Доказательство того, что тогда и только тогда, когда , аналогично доказательству теоремы 3.2.


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

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---