2015-02-18
609
 |
Р – регулярная грамматика;
КС – контекстно-свободная грамматика;
КЗ – контекстно-зависимая грамматика;
Тип 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)={ anbncn | n ³1} определяется грамматикой с правилами вывода:
|
|
|
1) S ® aSBC | abc;2) bC ® bc;
3) CB ® BC;4) cC ® cc;
5) BB ® bb.
в) Контекстно-свободный язык L (G)={(ab) n (cb) n | 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.
