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

Несколько определений

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

Грамматикой в нормальной форме Хомского (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], эквивалентную исходной, содержащую правила длины 0, 1 и 2. Удаление [math] \varepsilon [/math]-правил. Воспользуемся алгоритмом удаления [math] \varepsilon [/math]-правил из грамматики. Получим грамматику [math] \Gamma_2 [/math], эквивалентную исходной, но в которой нет [math]\varepsilon [/math]-правил. Удаление цепных правил. Воспользуемся алгоритмом удаления цепных правил из грамматики. Алгоритм работает таким образом, что новые [math] \varepsilon [/math]-правила не образуются. Получим грамматику [math] \Gamma_3 [/math], эквивалентную [math] \Gamma_1 [/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] n \ge 3 [/math] могло появиться [math] n-1 [/math] новых правил. При удалении [math] \varepsilon [/math]-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 3 раза. Всего цепных правил в грамматике не больше, чем [math] n^2 [/math], где [math] n [/math] — число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар (их не больше [math] n^2 [/math]) и производим добавление нецепных правил. Если максимальное количество нецепных правил среди всех возможных пар равно [math] k [/math], то добавить мы сможем не больше, чем [math] k*n^2 [/math]. Проанализируем ситуации, когда в правиле несколько терминалов: при таком порядке действий их однозначно два. Для каждого из таких правил мы добавляем еще по два нетерминала и правила.

[math]\triangleleft[/math]

Литература

• http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf