Тип 0. Грамматика называется грамматикой типа 0, если на ее правила вывода не наложено никаких ограничений, кроме тех, которые указаны в определении грамматики.

Тип 1.Грамматика называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид a®b, где a Î (V_T È V_N)⁺, b Î (V_T È V_N)^* и |a| £ |b|.

Тип 2. Грамматика называется контекстно-свободной грамматикой (КС-грамматикой), если ее правила вывода имеют вид: , где и

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

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

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

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

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

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

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

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

3.Примеры грамматик и языков