Алгоритм получения правил, не содержащих правил вывода нетерминальных символов.

1. Грамматика имеет набор правил R. Разобьем его наR₁иR₂ , причем вR₁будут входить только правила типаAB, гдеA,B€V_n

2. Для любого символа A_iстоит в левой части правила нетерминала построим подмножество правил (A_i) следующим образом, если существует

A_i  A_n ; A_n ηB , то в SA_i войдет A_i  ηB.

3. Строим новую грамматику, создающую следующий набор правил:

R=V_i=1^kS(A_i)vR_iгдеk– число нетерминальных символов, находящихся слева в правилах набораRподмножества. Построение грамматики будет эквивалентно исходной и не создаст правил нетерминалов.

Рассмотрим пример:

G:

R = {IaM , MA , AaA , AB , BbB , Bb}

V_t = {a , b}

V_n = {I , M , A , B}

R₁ = {M  A , A  B}

R₂ = {I  aM , A  aA₁ B  bB , B  b}

S(M) = {MaA , M  bB , M  b}

S(A) = {A  bB , A  b}

R = {M  aA , M  bB , M  b , A bB , A b , I  aM , A  aA , B  bB , B  b}

Грамматика правосторонняя или левосторонняя контекстно-свободная, создается правило нетерминал-нетерминал, может быть преобразовано к автоматному виду.

Грамматика, контекстно-свободная создающаяся и правосторонней и левосторонней не может быть преобразована а автоматному виду.

Если грамматика имеет правило вида:

AφAψ,φ,ψ€V^*φ≠ε, то она не может быть преобразована к контекстно-свободной.

Самовосстанавливающаяся грамматика, которая содержит правило вида: AφAψ, гдеφ,ψ– любые символы, причем не пустые не может быть преобразована к автоматному виду.

Данный вывод вытекает из вывода два.

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