Соотношение типов грамматик и языков представлено на рисунке 1.1.

Р – регулярная грамматика;

КС – контекстно-свободная грамматика;

КЗ – контекстно-зависимая грамматика;

Тип 0 – грамматика типа 0.

Рисунок 1.1 – Соотношение типов формальных языков и грамматик

Тип 3.Грамматика называется регулярной грамматикой (Р-грамматикой) выровненной вправо, если ее правила вывода имеют вид , где .

Грамматика называется регулярной грамматикой (Р-грамматикой) выровненной влево, если ее правила вывода имеют вид , где .

Определение Язык L(G) называется языком типа k, если его можно описать грамматикой типа k, где k – максимально возможный номер типа грамматики.

Пример Примеры различных типов формальных языков и грамматик по классификации Хомского. Терминалы будем обозначать строчными символами, нетерминалы – прописными буквами, начальный символ грамматики – S.

а) Язык типа 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 ® e.

б) Контекстно-зависимый язык L(G)={aⁿbⁿcⁿ | n³1} определяется грамматикой с правилами вывода:

1) S ® aSBC | abc ;2) bC ® bc;

3) CB ® BC;4) cC ® cc;

5) BB ® bb.

в) Контекстно-свободный язык L(G)={(ab)ⁿ(cb)ⁿ | n>0 } определяется грамматикой с правилами вывода:

1) S ® aQb | accb;

2) Q ® cSc.

г) Регулярный язык L(G)={w^ | wÎ{a, b}⁺, где нет двух рядом стоящих а} определяется грамматикой с правилами вывода:

1) S ® A^ | B^;

2) A ® a | Ba;

3) B ® b | Bb | Ab.