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

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

$A$$\rightarrow \,BC$ или

$A$$\rightarrow \,\alpha$ или

$S$$\rightarrow \,\varepsilon$,

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

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

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

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

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

Альтернативное определение

Некоторые источники определяют нормальную форму Хомского несколько иначе.

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

$A$$\rightarrow \,BC$ или

$A$$\rightarrow \,\alpha$

где $A$, $B$ и $C$ — нетерминалы, и $\alpha$ — терминальный символ. При использовании такого определения $B$ и $C$ могут быть начальными символами.

Это определение отличается от предыдущего, так как исключает возможность порождения пустой строки $\varepsilon$. По прежнему справедливо, что любая контекстно-свободная грамматика, порождающая язык $L$, может быть эффективно преобразована в нормальную форму Хомского, порождающую $L-\{\varepsilon \}$. Принципиальное преимущество последнего определения в том, что доказательства в целом немного упрощаются, так как каждый шаг вывода никогда не уменьшает длину результирующей строки. Разумеется, его недостаток состоит в том, что требуется отдельное рассмотрение случая, когда грамматика порождает $\varepsilon$.

Литература

• Michael Sipser Introduction to the Theory of Computation (англ.). — PWS Publishing, 1997. — ISBN 0-534-94728-X. (Pages 98-101 of section 2.1: context-free grammars. Page 156.)
• John Martin. Introduction to Languages and the Theory of Computation (англ.). — McGraw-Hill Education, 2003. — ISBN 0-07-232200-4. (Pages 237—240 of section 6.6: simplified forms and normal forms.)
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 4.)
• Michael A. Harrison Introduction to Formal Language Theory (неопр.). — Addison-Wesley, 1978. — ISBN 978-0201029550. (Pages 103—106.)