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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• (англ.) ( . (англ.) . — PWS Publishing, 1997. — ISBN 0-534-94728-X . (Pages 98-101 of section 2.1: context-free grammars. Page 156.)
• John Martin . (англ.) . — 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.)
• (англ.) ( . Introduction to Formal Language Theory (неопр.) . — Addison-Wesley , 1978. — ISBN 978-0201029550 . (Pages 103—106.)