Нормальная форма Хомского

Нормальная форма Хомского — свойство формальной грамматики, если все её продукции имеют вид:

${\displaystyle A}$${\displaystyle \rightarrow \,BC}$ или

${\displaystyle A}$${\displaystyle \rightarrow \,\alpha }$ или

${\displaystyle S}$${\displaystyle \rightarrow \,\epsilon }$,

где ${\displaystyle A}$, ${\displaystyle B}$ и ${\displaystyle C}$ — нетерминалы, ${\displaystyle \alpha }$ — терминальный символ (представляющий постоянное значение), ${\displaystyle S}$ — начальный символ, и ${\displaystyle \epsilon }$ — пустая строка. Также ни ${\displaystyle B}$, ни ${\displaystyle C}$ не может быть начальным символом.

Каждая грамматика в нормальной форме Хомского является контекстно-свободной, и наоборот, каждая контекстно-свободная грамматика может быть эффективно преобразована в эквивалентную грамматику в нормальной форме Хомского.

За исключением возможного правила ${\displaystyle S}$${\displaystyle \rightarrow \,\epsilon }$ (используемого, когда грамматика может порождать пустую строку), все правила грамматики в нормальной форме Хомского неукорачивающие; то есть, в процессе вывода строки каждая цепочка из терминалов и нетерминалов всегда имеет либо ту же длину, что и предыдущая, либо на один элемент больше. Вывод строки длины ${\displaystyle n}$ всегда занимает ровно ${\displaystyle 2n-1}$ шагов. Кроме того, так как все правила вывода нетерминалов переводят один нетерминал в ровно один терминал или в ровно два нетерминала, дерево разбора, основанное на грамматике в нормальной форме Хомского, составляет собой бинарное дерево, высота которого ограничена длиной строки.

Благодаря этим свойствам, многие доказательства в теории формальных языков и вычислимости используют нормальную форму Хомского. Эти свойства также служат основой различных эффективных алгоритмов — например, CYK-алгоритм, определяющий, может ли данная строка порождаться данной грамматикой, использует нормальную форму Хомского.

Названа по имени Ноама Хомского, американского лингвиста, предложившего иерархию Хомского.