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

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

Нормальная форма Хомского в информатике.

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

A\rightarrow\, BC или
A\rightarrow\, α или
S\rightarrow\, ε

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

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

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

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

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

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

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

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

A \rightarrow\, BC или
A \rightarrow\, α

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

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

Список литературы[править | править вики-текст]

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

См. также[править | править вики-текст]

Нормальная форма Курода Форма Бэкуса — Наура