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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

или
или
,

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

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

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

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

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

Альтернативное определение[править | править вики-текст]

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

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

или

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

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

Литература[править | править вики-текст]

  • 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, 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.)