Нормальная форма Хомского — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 24: Строка 24:
 
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex>\varepsilon </tex>-правил.
 
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex>\varepsilon </tex>-правил.
 
# Удаление цепных правил.
 
# Удаление цепных правил.
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \Gamma_1 </tex>.
+
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \Gamma </tex>.
 
# Удалим бесполезные символы.
 
# Удалим бесполезные символы.
 
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.
 
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.
 
# Уберём ситуации, когда в правиле встречаются несколько терминалов.
 
# Уберём ситуации, когда в правиле встречаются несколько терминалов.
#:Для всех правил вида <tex> A \rightarrow u_1 u_2</tex> (где <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на переменные <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из нетерминалов.  
+
#:Для всех правил вида <tex> A \rightarrow u_1 u_2</tex> (где <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на новые нетерминалы <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из двух нетерминалов.  
 
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
 
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
Заметим, что размеры грамматики при таком порядке действий возрастают полиномиально. При удалении длинных правил из каждого правила длины  <tex> n \ge 3 </tex> могло появиться <tex> n-1 </tex> новых правил. При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 3 раза. Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар (их не больше <tex> n^2 </tex>) и производим добавление нецепных правил. Если максимальное количество нецепных правил среди всех возможных пар равно <tex> k </tex>, то добавить мы сможем не больше, чем <tex> k \cdot n^2 </tex>. Проанализируем ситуации, когда в правиле несколько терминалов: при таком порядке действий их однозначно два. Для каждого из таких правил мы добавляем еще по два нетерминала и правила.
+
 
 +
Заметим, что размеры грамматики при таком порядке действий возрастают полиномиально.
 +
 
 +
При удалении длинных правил из каждого правила длины  <tex> k \ge 3 </tex> могло появиться <tex> k-1 </tex> новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.
 +
 
 +
При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 3 раза.
 +
 
 +
Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна <tex> k </tex>, то размер грамматики возрастет не больше, чем на <tex> k \cdot n^2 </tex>.
 +
 
 +
Наконец, на последнем шаге может произойти добавление не более, чем <tex>|\Sigma|</tex> (<tex>\Sigma</tex> {{---}} алфавит грамматики) новых правил, причем все они будут длины 1.
 
}}
 
}}
  
 
==Литература==
 
==Литература==
 
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf
 
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf

Версия 16:58, 24 января 2012

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

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

  1. Уберём длинные правила.
    Воспользуемся алгоритмом удаления длинных правил из грамматики. Получим грамматику [math] \Gamma_1 [/math], эквивалентную исходной, содержащую правила длины 0, 1 и 2.
  2. Удаление [math] \varepsilon [/math]-правил.
    Воспользуемся алгоритмом удаления [math] \varepsilon [/math]-правил из грамматики. Получим грамматику [math] \Gamma_2 [/math], эквивалентную исходной, но в которой нет [math]\varepsilon [/math]-правил.
  3. Удаление цепных правил.
    Воспользуемся алгоритмом удаления цепных правил из грамматики. Алгоритм работает таким образом, что новые [math] \varepsilon [/math]-правила не образуются. Получим грамматику [math] \Gamma_3 [/math], эквивалентную [math] \Gamma [/math].
  4. Удалим бесполезные символы.
    Воспользуемся алгоритмом удаления бесполезных символов из грамматики. Так как [math] \Gamma_3 [/math] эквивалентна [math] \Gamma [/math], то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые [math]\varepsilon[/math]-правила и цепные правила не могли появиться.
  5. Уберём ситуации, когда в правиле встречаются несколько терминалов.
    Для всех правил вида [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] k \ge 3 [/math] могло появиться [math] k-1 [/math] новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.

При удалении [math] \varepsilon [/math]-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 3 раза.

Всего цепных правил в грамматике не больше, чем [math] n^2 [/math], где [math] n [/math] — число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна [math] k [/math], то размер грамматики возрастет не больше, чем на [math] k \cdot n^2 [/math].

Наконец, на последнем шаге может произойти добавление не более, чем [math]|\Sigma|[/math] ([math]\Sigma[/math] — алфавит грамматики) новых правил, причем все они будут длины 1.
[math]\triangleleft[/math]

Литература