Рассмотрим классификацию грамматик (предложенную Н.Хомским), основанную на виде их правил.
Определение. Пусть дана грамматика G = (N, T, P, S). Тогда
(1) если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений.
(2) если
(3) если каждое правило грамматики имеет вид
(4) если каждое правило грамматики имеет вид либо
Легко видеть, что грамматика в примере 2.5 - неукорачивающая, в примере 2.6 - контекстно-свободная, в примере 2.7 - праволинейная.
Язык, порождаемый грамматикой типа i, называют языком типа i. Язык типа 0 называют также языком без ограничений, язык типа 1 - контекстно-зависимым (КЗ), язык типа 2 - контекстно-свободным (КС), язык типа 3 - праволинейным.