Классификация грамматик по Хомскому Т0. Фразовая Т1. Контекстно-зависимая Р :, где (V T V N ) +, (V T V N ) * и | | | |, Т2. Контекстно-свободная Р : А, где А V N, V * Т3. Регулярная, выровненная вправо(влево) А, S G = (V T, V N, P, S) P: A aB | a, где a V T ; A, B V N A Ba | a

Соотношение типов грамматик и языков Т0 КЗ КС Р Р – регулярная грамматика; КС – контекстно-свободная грамматика; КЗ – контекстно-зависимая грамматика; Т0 – фразовая грамматика.

Язык типа 0 L(G)= 1) S aaCFD;2) AD D; 3) F AFB | AB;4) Cb bC; 5) AB bBA;6) CB C; 7) Ab bA;8) bCD.

Контекстно-зависимый язык L(G)={a n b n c n | n 1} 1) S aSBC | aBC;2) CB BC; 3) aB ab;4) bB bb; 5) bC bc;6) cC cc.

Контекстно-свободный язык L(G)={(ac) n (cb) n | n>0} 1) S aQb | accb; 2) Q cSc.

Регулярный язык L(G)={ | {a, b} +, где нет двух рядом стоящих а} 1) S A | B ; 2) A a | Ba; 3) B b | Bb | Ab.