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

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

Грамматикой в нормальной форме Хомского (англ. 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]

Пример

Текущий шаг	Грамматика после применения правила
0. Исходная грамматика	[math]S\rightarrow aXbX|aZ[/math] [math]X\rightarrow aY|bY|\varepsilon[/math] [math]Y\rightarrow X|cc[/math] [math]Z\rightarrow ZX[/math]
1. Удаление длинных правил	[math]S\rightarrow aS_{1}|aZ[/math] [math]X\rightarrow aY|bY|\varepsilon[/math] [math]Y\rightarrow X|cc[/math] [math]Z\rightarrow ZX[/math] [math]S_{1}\rightarrow XS_{2}[/math] [math]S_{2}\rightarrow yX[/math]
2. Удаление [math]\varepsilon[/math]-правил	[math]S\rightarrow aS_{1}|aZ[/math] [math]X\rightarrow aY|bY[/math] [math]Y\rightarrow aY|bY|cc[/math] [math]Z\rightarrow ZX[/math] [math]S_{1}\rightarrow XS_{2}|S_{2}[/math] [math]S_{2}\rightarrow yX|y[/math]
3. Удаление цепных правил	[math]S\rightarrow aS_{1}|aZ[/math] [math]X\rightarrow aY|bY[/math] [math]Y\rightarrow aY|bY|cc[/math] [math]Z\rightarrow ZX[/math] [math]S_{1}\rightarrow XS_{2}|yX|y[/math] [math]S_{2}\rightarrow yX|y[/math]
4. Удаление бесполезных символов	[math]S\rightarrow aS_{1}[/math] [math]X\rightarrow aY|bY[/math] [math]Y\rightarrow aY|bY|cc[/math] [math]S_{1}\rightarrow XS_{2}|yX|y[/math] [math]S_{2}\rightarrow yX|y[/math]
5. Уберём ситуации, когда в правиле встречаются несколько терминалов.	[math]S\rightarrow S_{3}S_{1}[/math] [math]X\rightarrow S_{3}Y|X_{1}Y[/math] [math]Y\rightarrow S_{3}Y|X_{1}Y|Y_{1}Y_{1}[/math] [math]S_{1}\rightarrow XS_{2}|S_{4}X|y[/math] [math]S_{2}\rightarrow S_{4}X|y[/math] [math]S_{3}\rightarrow a[/math] [math]S_{4}\rightarrow y[/math] [math]X_{1}\rightarrow b[/math] [math]Y_{1}\rightarrow c[/math]

См. также

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

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

• Wikipedia — Chomsky normal form
• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 280с. : ISBN 5-8459-0261-4 (рус.)