Классификация грамматик по Хомскому.

1. Грамматика типа 0 или общего вида

φ ψ , φ ≠e(e– символ конца)

φ может содержать не только терминальные символы

| ώ| - длина цепочки – число символов цепочки.

| φ | < | ψ |

Могут быть правила, которые укорачивают цепочки. Эта грамматика не имеет практического использования.

2. Грамматика типа 1 или непосредственных составляющих.

Это контекстно-зависимая грамматика и неукорачивает длину цепочки.

ξ₁φ ξ₂ ξ₁ψ ξ₂

ξ₁ξ₂φ ψ € V^*

Грамматика контекстно-зависимая и неукорачивающая.

G₈

V_т = {a , b , с, d}

I

V_n = {I , A , B}

R = {IaAI , AIAA , AAAABA , aBA  bcdA , bI  ba}

3. Грамматика типа 2 или контекстно-свободная

A € V_n , ώ € V^*

G₉

V_т = {a , b}

I

V_n = {I }

R = {IcIa , IbIb , Iaa , I  bb}

I  aIa  abIba  abaIaba  ababbaba

L(G₉) = {xx¹ ; x € V_т^*}

4. Грамматика типа 3 или автоматная

1. левосторонняя

A  a , A  Ba

2. правосторонняя

A  a , A  aB

A , B € V_n , a € V_т

В грамматике либо левосторонняя, либо правосторонняя.

AaA;AAa– рекурсивное

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

G₁₀

V_т = {a , b}

I

V_n = {I , A}

R = {IaI , IaA , AbA , A  b}

L(G₁₀) = {aⁿb^m , a,b € V_т , n>0 , m>0 }

L₀<=L_I<=L_II<=L_III

Язык L_IIIболее узок, чем языкL_IIи так далее.