Иерархия Хомского - классификация формальных грамматик и задаваемых ими языков, согласно которой они делятся на 4 класса по их условной сложности. (Класс 0, Класс 1, Класс 2, Класс 3)
К нулевому классу относятся все формальные грамматики. Элементы этого класса называются неограниченными грамматиками. Они задают все языки, которые могут быть распознаны машиной Тьюринга. Эти языки также известны как рекурсивно перечислимые.
Правила можно записать в виде: $\alpha \to \beta$, где $\alpha$ - любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а $\beta$ - любая цепочка символов из алфавита.
$S \to aBcc$ $B \to A$ $BAA \to d$ $Ac \to B$ $A \to AAA | dB$
Выведем в данной грамматике строку addd:
$S \rArr aBcc \rArr aAcc \rArr aBc \rArr aAc \rArr aB \rArr aA \rArr adB \rArr adA \rArr adAAA \rArr addBAA \rArr addd$
Класс 1 представлен неукорачивающими и контекстно-зависимыми грамматиками
Неукорачивающаяся грамматика - это формальная грамматика, всякое правило из $P$ которой имеет вид $\alpha \to \beta$, где $\alpha, \beta \in \{\Sigma \cup Г\}^+$ и $|\alpha| ≤ |\beta|$ (возможно правило $S \to \varepsilon$, но тогда $S$ не встречается в правых частях правил)
Контекстно-зависимая грамматика - это формальная грамматика, всякое правило из $P$ которой имеет вид $\alpha A \beta \to \alpha \gamma \beta$, где $\alpha, \beta \in \{\Sigma \cup Г\}^*$, $A \in Г$ и $\gamma \in \{\Sigma \cup Г\}^+$ (возможно правило $S \to \varepsilon$, но тогда S не встречается в правых частях правил)
$L = \{w \in \Sigma^* | w = 0^n1^n2^n, n≥ 1\}$
$S \to 012$ $S \to 0AS2$ $A0 \to 0A$ $A1 \to 11$
Второй класс составляют контекстно-свободные грамматики, которые задают контекстно-свободные языки.