КЛАССИФИКАЦИЯ ГРАММАТИК ПО ХОМСКОМУ.

Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик.
Грамматика типа 0 (произвольная) – это грамматика произвольного вида, без ограничений на вид продукций грамматики.
Продукции имеют вид , где .
Грамматика типа 1 (контекстная грамматика) – это грамматика, все продукции которой имеют вид , где . Произвольный нетерминальный знак может быть заменен на строку если знак встречается в контексте и , где -левый контекст, — правый контекст.
Пример: При анализе текста встретилось слово коса , понять смысл которого без начального и конечного текста невозможно (девичья коса, железная коса, речная коса).

Определение. УКОРАЧИВАЮЩИЕ ГРАММАТИКИ – это грамматики у которых существуют продукции вида .

Определение. НЕУКОРАЧИВАЮЩИЕ ГРАММАТИКИ – это грамматики у которых существуют продукции вида , где .

Замечание. Иногда контекстные грамматики отождествляются с неукорачивающими. Это не противоречит классификации, только приводит к тому, что укорачивающие грамматики не рассматриваются.

Грамматика типа 2 (контекстно-свободная) – это грамматика, все продукции которой имеют вид , где .
Грамматика типа 3 (регулярная) – это грамматика, все продукции которой имеют вид или , где .
Язык называется языком типа ,если существует порождающая его грамматика типа .
Очевидно, что если ввести классы грамматик и обозначить всевозможные грамматики типа 0 как , всевозможные грамматики типа 1 — , всевозможные грамматики типа 2 — , всевозможные грамматики типа 3 — .Тогда получим

Предполагается, что каждый частный тип грамматики включен в состав класса граматики более общего типа.

Замечание. Один и тот же язык может быть порожден грамматиками различных типов.

Замечание. Выразительные возможности грамматик убывают по мере увеличения номера ее типа.