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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 46 промежуточных версий 9 участников)
Строка 1: Строка 1:
==Несколько определений==
 
 
 
{{Определение
 
{{Определение
|definition=Грамматикой в '''нормальной форме Хомского''' (''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержатся правила только следующего вида:
+
|definition=Грамматикой в '''нормальной форме Хомского''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться правила только следующего вида:
<tex>A \rightarrow B C </tex>,
+
:<tex>A \rightarrow B C </tex>,
  
<tex>A \rightarrow a </tex>,
+
:<tex>A \rightarrow a </tex>,
  
<tex>S \rightarrow \varepsilon </tex>,
+
:<tex>S \rightarrow \varepsilon </tex>,
  
 
где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.
 
где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.
}}
 
 
{{Определение
 
|definition=Пара нетерминалов <tex> A </tex> и <tex> B </tex> называется '''узловой''', если <tex> A \Rightarrow^* B </tex>.
 
 
<tex> \forall A </tex> выполняется <tex> (A, A) </tex> {{---}} узловая пара.
 
 
Если <tex> (A, B) </tex> {{---}} узловая пара, а <tex> B \rightarrow C </tex>, то <tex> (A, C) </tex> тоже узловая пара.
 
}}
 
 
{{Определение
 
|definition=Правило <tex> A \rightarrow w </tex> называется '''смешанным''', если <tex> w </tex> содержит хотя бы один терминал и хотя бы один нетерминал. 
 
 
}}
 
}}
  
Строка 29: Строка 15:
 
|statement=Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.
 
|statement=Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.
 
|proof=
 
|proof=
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной форме Хомского необходимо выполнить четыре шага. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.
+
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной форме Хомского необходимо выполнить пять шагов. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.
  
 +
# Уберём длинные правила.
 +
#: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1
 +
</tex>, эквивалентную исходной, содержащую правила длины <tex>0, 1</tex> и <tex>2</tex>.
 
# Удаление <tex> \varepsilon </tex>-правил.
 
# Удаление <tex> \varepsilon </tex>-правил.
##Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим <tex> \Gamma_1 </tex>.
+
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex>\varepsilon </tex>-правил.
# Преобразование узловых пар.
+
# Удаление цепных правил.
#:Для каждой узловой пары <tex> (A, B) </tex>, найдем все правила <tex> B \rightarrow w </tex>, где <tex> w </tex> {{---}} произвольная строка терминалов и нетерминалов,  и добавим <tex> A \rightarrow w </tex> в <tex> \Gamma_2 </tex>.
+
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \Gamma </tex>.
# Преобразование смешанных правил.
+
# Удалим бесполезные символы.
#:Если <tex> A \rightarrow w </tex> {{---}} смешанное правило, то можно представить <tex> w </tex> в виде <tex> w=v_0 c_1 v_1 c_2 ... v_{n-1} c_n v_n </tex>, где <tex> v_i </tex> {{---}} строка нетерминалов, а <tex> c_i </tex> является терминалом. Тогда для каждого <tex> c_i </tex> добавим нетерминал <tex> C_i </tex> и правило <tex> C_i \rightarrow c_i </tex> в <tex> \Gamma_3 </tex>. Получим <tex> w'=v_0 C_1 v_1 C_2 ... v_{n-1} C_n v_n </tex>. Добавим правило <tex> A \rightarrow w' </tex> в <tex> \Gamma_3 </tex>.  
+
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.
# Преобразование длинных правил.
+
# Уберём ситуации, когда в правиле встречаются несколько терминалов.
#:Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим <tex> \Gamma_4 </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_4 </tex> в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.  
+
Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до <tex>O(2^{\left| \Gamma \right|})</tex>. Третье правило идет после второго, потому что после удаления <tex>\varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьего и второго, так как они могут порождать бесполезные символы.
 +
 
 +
При таком порядке действий размеры грамматики возрастают полиномиально.
 +
 
 +
После удалении длинных правил из каждого правила длины  <tex> k \geqslant 3 </tex> могло появиться <tex> k-1 </tex> новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.
 +
 
 +
При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины <tex>0, 1</tex> и <tex>2</tex>, размеры грамматики могли вырасти не больше, чем в <tex>3</tex> раза.
 +
 
 +
Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна <tex> k </tex>, то размер грамматики возрастет не больше, чем на <tex> k \cdot n^2 </tex>.
 +
 
 +
Наконец, на последнем шаге может произойти добавление не более, чем <tex>|\Sigma|</tex> (<tex>\Sigma</tex> {{---}} алфавит грамматики) новых правил, причем все они будут длины <tex>1</tex>.
 
}}
 
}}
  
==Литература==
+
== Пример ==
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf
+
{| border="1" class="wikitable" style="width: 500px; height: 500px; float: left;"
 +
!style="background:#41aef0"|Текущий шаг
 +
!style="background:#41aef0"|Грамматика после применения правила
 +
|-
 +
|''0. Исходная грамматика''
 +
|<tex>S\rightarrow aXbX|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|cc</tex><br> <tex>Z\rightarrow ZX</tex>
 +
|-
 +
|''1. Удаление длинных правил''
 +
|<tex>S\rightarrow aS_{1}|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}</tex> <br> <tex>S_{2}\rightarrow yX</tex>
 +
|-
 +
|''2. Удаление <tex>\varepsilon</tex>-правил''
 +
|<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{2}</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
 +
|-
 +
|''3. Удаление цепных правил''
 +
|<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
 +
|-
 +
|''4. Удаление бесполезных символов''
 +
|<tex>S\rightarrow aS_{1}</tex> <br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
 +
|-
 +
|''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.''
 +
|<tex>S\rightarrow S_{3}S_{1}</tex><br> <tex>X\rightarrow S_{3}Y|X_{1}Y</tex> <br> <tex>Y\rightarrow S_{3}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{4}X|y</tex> <br> <tex>S_{2}\rightarrow S_{4}X|y</tex>  <br> <tex>S_{3}\rightarrow a</tex> <br> <tex>S_{4}\rightarrow y</tex> <br> <tex>X_{1}\rightarrow b</tex>  <br> <tex>Y_{1}\rightarrow c</tex>
 +
|}
 +
<div style="clear:both;"></div>
 +
 
 +
== См. также  ==
 +
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
 +
* [[Нормальная_форма_Куроды | Нормальная форма Куроды]]
 +
* [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах | Приведение грамматики к ослабленной нормальной форме Грейбах]]
 +
 
 +
==Источники информации==
 +
* [[wikipedia:en:Chomsky normal form | Wikipedia {{---}} Chomsky normal form]]
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528с. : ISBN 5-8459-0261-4 (рус.)
 +
 
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Нормальные формы КС-грамматик]]

Текущая версия на 19:17, 4 сентября 2022

Определение:
Грамматикой в нормальной форме Хомского (англ. 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], эквивалентную исходной, содержащую правила длины [math]0, 1[/math] и [math]2[/math].
  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]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. — 528с. : ISBN 5-8459-0261-4 (рус.)