Пусть задана регулярная граматика правила α имеет вид

G=<N,T,P,S>

B::=UA

B::=U, где UЄT*, A,BЄN

Тогда конечный автомат M=<Σ,Q,Δ,I,F> допускающий тот же  самый язык, что пораждает регулярная грамматика G строиться след образом:

Σ=T

Q=Nv{Z},Z непринадлежитN и T, Z-заключительное состояние

I={S}

F={Z}

Отображение Δ строиться след образом:

- каждому правилу  подстановок в грамматике G, где  B::=UA ставиться в  соответствие команда (B,U)àA

- каждому правилу  подстановок в грамматике G, где  B::=U ставиться в  соответствие команда (B,U)àZ

Возможен  и обратный  переход: конечный  автомат M=<Σ,Q,Δ,I,F> ставиться  в соответствие  регулярная грамматика G=<N,T,P,S>

T=Σ

N=Q

S={I}

Множество правил подстановок P строиться следующим образом:

Каждой команде автомата (qi,aj)àqx ставиться в соответсвие правило подстановки qi::=ajqx. Если qx принадлежит Q, но  qx непринадлежит F либо qi::=aj если qx принадлежит F.

Пример:

 G=<N,T,P,S>

N={S,K}, T={b,c}

P: S::=b|bK

K::=b|c|bK|cK

1. Σ={b,c}
2. Q={S,K}v{Z}={S,K,Z}
3. I=S
4. F=Z
5. Δ:

(S,b)àZ

(S,bàK

(K,b)àZ

(K,c)àZ

(K,b)àK

(K,c)àK