Иерархия Хомского

---

Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским.

Согласно Хомскому, формальные грамматики можно разделить на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие всех её правил (продукций) некоторым схемам.

Грамматика с фразовой структурой G — это алгебраическая структура, упорядоченная четвёрка (V_T, V_N, P, S), где^[1]:

Здесь ${\displaystyle V^{*}}$ — множество всех строк над алфавитом ${\displaystyle V}$, а ${\displaystyle V^{+}}$ — множество непустых строк над алфавитом ${\displaystyle V}$.

К типу 0 по классификации Хомского относятся неограниченные грамматики — грамматики с фразовой структурой, то есть все без исключения формальные грамматики. Правила можно записать в виде:

где ${\displaystyle \alpha \in V^{+}}$ — любая непустая цепочка, содержащая хотя бы один нетерминальный^[2] символ, а ${\displaystyle \beta \in V^{*}}$ — любая цепочка символов из алфавита.

---