Классификация грамматик по Хомскому осуществляется по структуре их правил вывода. Выделяется четыре типа грамматик.

Определение Цепочка b Î (VTÈVN)* выводима из цепочки в грамматике (обозначается aÞ*b), если существует последовательность цепочек (n³0) такая, что .

ПримерВ грамматике G₁ SÞ*000111, т.к. существует вывод .

ОпределениеЯзыком, порожденным грамматикой ,называется множество всех цепочек в алфавите V_T, которые выводимы из начального символа грамматики S c помощью правил множества Р, т.е. множество .

ПримерДля грамматики G₁ язык L(G₁)={0ⁿ1ⁿ | n³0}.

Определение Цепочка , для которой существует вывод SÞ*a, называется сентенциальной формой или сентенцией в грамматике .

ОпределениеЯзыком, порожденным грамматикой G называется множество терминальных сентенциальных форм грамматики.

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

Классификация грамматик по Хомскому осуществляется по структуре их правил вывода. Выделяется четыре типа грамматик.