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

Определение:

Грамматикой в нормальной форме Хомского (англ. Chomsky normal form) называется контекстно-свободная грамматика, в которой могут содержаться правила только следующего вида: [math]A \rightarrow B C [/math], [math]A \rightarrow a [/math], [math]S \rightarrow \varepsilon [/math], где [math] a [/math] — терминал, [math] A, B, C [/math] — нетерминалы, [math] S [/math] — стартовая вершина, [math] \varepsilon [/math] — пустая строка, стартовая вершина не содержится в правых частях правил.

Приведение грамматики к нормальной форме Хомского

Теорема:

Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.

Доказательство:

[math]\triangleright[/math]

Рассмотрим контекстно-свободную грамматику [math] \Gamma [/math]. Для приведения ее к нормальной форме Хомского необходимо выполнить пять шагов. На каждом шаге мы строим новую [math] \Gamma_i [/math], которая допускает тот же язык, что и [math] \Gamma [/math]. Уберём длинные правила. Воспользуемся алгоритмом удаления длинных правил из грамматики. Получим грамматику [math] \Gamma_1 [/math], эквивалентную исходной, содержащую правила длины [math]0, 1[/math] и [math]2[/math]. Удаление [math] \varepsilon [/math]-правил. Воспользуемся алгоритмом удаления [math] \varepsilon [/math]-правил из грамматики. Получим грамматику [math] \Gamma_2 [/math], эквивалентную исходной, но в которой нет [math]\varepsilon [/math]-правил. Удаление цепных правил. Воспользуемся алгоритмом удаления цепных правил из грамматики. Алгоритм работает таким образом, что новые [math] \varepsilon [/math]-правила не образуются. Получим грамматику [math] \Gamma_3 [/math], эквивалентную [math] \Gamma [/math]. Удалим бесполезные символы. Воспользуемся алгоритмом удаления бесполезных символов из грамматики. Так как [math] \Gamma_3 [/math] эквивалентна [math] \Gamma [/math], то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые [math]\varepsilon[/math]-правила и цепные правила не могли появиться. Уберём ситуации, когда в правиле встречаются несколько терминалов. Для всех правил вида [math] A \rightarrow u_1 u_2[/math] (где [math] u_i [/math] — терминал или нетерминал) заменим все терминалы [math] u_i [/math] на новые нетерминалы [math] U_i [/math] и добавим правила [math] U_i \rightarrow u_i [/math]. Теперь правила содержат либо одиночный терминал, либо строку из двух нетерминалов. Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и [math] \Gamma [/math]. Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до [math]O(2^{\left| \Gamma \right|})[/math]. Третье правило идет после второго, потому что после удаления [math]\varepsilon[/math]-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено после третьего, так как оно может порождать бесполезные символы. При таком порядке действий размеры грамматики возрастают полиномиально. После удалении длинных правил из каждого правила длины [math] k \geqslant 3 [/math] могло появиться [math] k-1 [/math] новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое. При удалении [math] \varepsilon [/math]-правил из грамматики, содержащей правила длины [math]0, 1[/math] и [math]2[/math], размеры грамматики могли вырасти не больше, чем в [math]3[/math] раза. Всего цепных правил в грамматике не больше, чем [math] n^2 [/math], где [math] n [/math] — число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна [math] k [/math], то размер грамматики возрастет не больше, чем на [math] k \cdot n^2 [/math]. Наконец, на последнем шаге может произойти добавление не более, чем [math]|\Sigma|[/math] ([math]\Sigma[/math] — алфавит грамматики) новых правил, причем все они будут длины [math]1[/math].

[math]\triangleleft[/math]

Пример

Рассмотрим грамматику для языка правильных скобочных последовательностей: [math]S\rightarrow \varepsilon|(S)|SS[/math].

1. Удалим длинные правила и получим грамматику [math] \begin{array}{l l} S\rightarrow \varepsilon|A)|SS\\ A\rightarrow (S \end{array} [/math].
2. Удалим ε правила - [math] \begin{array}{l l} S\rightarrow \varepsilon|S'\\ S'\rightarrow A)|S'S'\\ A\rightarrow (S'|( \end{array} [/math].
3. Удалим цепные правила - [math] \begin{array}{l l} S\rightarrow \varepsilon|A)|S'S'\\ S'\rightarrow A)|S'S'\\ A\rightarrow (S'|( \end{array} [/math].
4. Заменим терминалы на нетерминалы - [math] \begin{array}{l l} S\rightarrow \varepsilon|AB|S'S'\\ S'\rightarrow AB|S'S'\\ A\rightarrow CS'|(\\ C\rightarrow (\\ B\rightarrow ) \end{array} [/math].

См. также

• Контекстно-свободные грамматики
• Нормальная форма Куроды
• Приведение грамматики к ослабленной нормальной форме Грейбах

Источники информации

• Wikipedia — Chomsky normal form
• http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf
• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 280с. : ISBN 5-8459-0261-4 (рус.)