Изменения

Перейти к: навигация, поиск

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

3278 байт добавлено, 21:38, 21 декабря 2015
м
Источники информации
==Несколько определений==
 
{{Определение
|definition=Грамматикой в '''нормальной форме Хомского ''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержатся содержаться правила только следующего вида::<tex>A \rightarrow B C </tex>.,
:<tex>A \rightarrow a </tex>.,
:<tex>S \rightarrow \varepsilon </tex>.,
(где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил).
}}
==Приведение грамматики к нормальной форме Хомского== {{ОпределениеТеорема|statement=Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.|definitionproof=Вершина называется обнуляемойРассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной форме Хомского необходимо выполнить пять шагов. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, если что и <tex> \Gamma </tex>. # Уберём длинные правила.#: Воспользуемся [[Удаление длинных правил из нее можно прямо или косвенно получить пустую строкуграмматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1 </tex>, эквивалентную исходной, содержащую правила длины <tex>0, 1</tex> и <tex>2</tex>.# Удаление <tex> \varepsilon </tex>-правил. Если #:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex> A \rightarrow varepsilon </tex>-правил.# Удаление цепных правил.#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \Gamma </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> \Gamma </tex>.
Если Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до <tex> A O(2^{\left| \rightarrow B_1....B_n Gamma \right|})</tex>. Третье правило идет после второго, где все потому что после удаления <tex> B_i \varepsilon</tex> обнуляемые-правил, то <tex> A </tex> тоже обнуляемаямогут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьего и второго, так как они могут порождать бесполезные символы.}}
{{Определение|definition=Пара вершин <tex> A </tex> и <tex> B </tex> называется узловой, если <tex> A \Rightarrow^* B </tex>При таком порядке действий размеры грамматики возрастают полиномиально.
После удалении длинных правил из каждого правила длины <tex> k \forall A geqslant 3 </tex> выполняется могло появиться <tex> (A, A) k-1 </tex> {{---}} узловая парановых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.
Если При удалении <tex> (A, B) \varepsilon </tex> {{---}} узловая параправил из грамматики, а содержащей правила длины <tex> B \rightarrow C 0, 1</tex> и <tex>2</tex>, то размеры грамматики могли вырасти не больше, чем в <tex> (A, C) 3</tex> тоже узловая парараза.}}
==Преобразование Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна <tex> k </tex>, то размер грамматики в нормальную форму Хомского==возрастет не больше, чем на <tex> k \cdot n^2 </tex>.
Рассмотрим [[Контекстно-свободные грамматикиНаконец, выводна последнем шаге может произойти добавление не более, лево- и правосторонний вывод, дерево разборачем <tex>|\Sigma|контекстно-свободную грамматику]] </tex> (<tex> \Gamma Sigma</tex>. Для преобразования ее в нормальную форму Хомского необходимо избавиться от {{---}} алфавит грамматики) новых правил следующего типа, причем все они будут длины <tex>1</tex>.}}
== Пример =={| 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> S_0 Y\rightarrow X|cc</tex> с новым правилом <br> <tex> S_0 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> S Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{---2}} старая стартовая вершина. Получим </tex> <br> <tex> S_{2}\Gamma_1 rightarrow yX</tex>|-|''2.# Удаление <tex> \varepsilon- </tex> -правил.''##Если |<tex> A S\rightarrow aS_{1}|aZ</tex><br> <tex>X\varepsilon rightarrow aY|bY</tex>, то выкинем такое правило.##Если <br> <tex> A Y\rightarrow w aY|bY|cc</tex>, где <br> <tex> w Z\rightarrow ZX</tex> не содержит <br> <tex> S_{1}\varepsilon rightarrow XS_{2}|S_{2}</tex> и обнуляемых переменных, то добавим такое правило в <br> <tex> S_{2}\Gamma_2 rightarrow yX|y</tex>|-|''3.Удаление цепных правил''##Если |<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex> A X\rightarrow w aY|bY</tex>, причем <br> <tex> w Y\rightarrow aY|bY|cc</tex> содержит обнуляемые переменные, то представим <br> <tex> w Z\rightarrow ZX</tex> в виде <br> <tex> w=w_0 N_0 w_1 N_1 ... w_S_{n-1} N_\rightarrow XS_{n2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex> |-|''4. Удаление бесполезных символов''|<tex>S\rightarrow aS_{1} w_n N_n </tex>, где <br> <tex>X\rightarrow aY|bY</tex> <br> <tex> N_i 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> w_i S\rightarrow S_{3}S_{1}</tex> не содержит обнуляемых переменных. Добавим в <br> <tex> X\Gamma_2 rightarrow S_{3}Y|X_{1}Y</tex> все правила, которые можно получить удалением всевозможных комбинаций <br> <tex> N_i Y\rightarrow S_{3}Y|X_{1}Y|Y_{1}Y_{1}</tex> из <br> <tex> w S_{1}\rightarrow XS_{2}|S_{4}X|y</tex>. Таких вариантов будет <br> <tex> S_{2^n }\rightarrow S_{4}X|y</tex>. #:Если стартовая вершина <br> <tex> S_{3}\Gamma_1 rightarrow a</tex> является обнуляемой, то добавим в <br> <tex> S_{4}\Gamma_2 rightarrow y</tex> правило <br> <tex> S_0 X_{1}\rightarrow b</tex> <br> <tex>Y_{1}\varepsilon rightarrow c</tex>.# Удаление вершин, которые могут породить друг друга.|}# Преобразование правил с длинной правой частью.<div style="clear:both;"></div>
== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Куроды | Нормальная форма Куроды]]
* [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах | Приведение грамматики к ослабленной нормальной форме Грейбах]]
Рассмотрим ==Источники информации==* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбораwikipedia:en:Chomsky normal form |контекстноWikipedia {{-свободную грамматику]] <tex>\Gamma</tex>, из которой удалены [[Удаление бесполезных символов из грамматики|бесполезные символы]], [[Удаление eps-правил из грамматики|<tex>\varepsilon</tex>-правила}} Chomsky normal form]], [[Удаление длинных правил из грамматики|длинные правила]] и [[Удаление цепных правил из грамматики|цепные правила]]. Такая грамматика содержит только правила следующего вида:*<tex>A \rightarrow BC</tex>*<tex>A \rightarrow Bc</tex>*<tex>A \rightarrow bC</tex>*<tex>A \rightarrow bc</tex>*<tex>A \rightarrow a</tex>*возможно''Хопкрофт Д., <tex>S \rightarrow \varepsilon</tex> (при условииМотвани Р., что <tex>S</tex> не содержится Ульман Д.'' — '''Введение в правых частях правил)Избавимся от правилтеорию автоматов, в правых частях которых записаны два символаязыков и вычислений''', один из которых является терминалом2-е изд. : Пер. с англ. — Москва, то есть правил вида <tex>A \rightarrow Bc</tex>Издательский дом «Вильямс», <tex>A \rightarrow bC</tex> и <tex>A \rightarrow bc</tex>2002. Введем для каждого терминала <tex>a</tex> "персональный" нетерминал <tex>N_a</tex>— 528с. Затем правила вида <tex>A \rightarrow Bc</tex> заменим парой правил <tex>A \rightarrow BN_c</tex> и <tex>N_c \rightarrow c</tex>, правила вида <tex>A \rightarrow bC</tex> заменим парой правил <tex>A \rightarrow N_bC</tex> и <tex>N_b \rightarrow b</tex>, а правила вида <tex>A \rightarrow bc</tex> {{: ISBN 5-8459-0261-}} тройкой правил <tex>A \rightarrow N_bN_c</tex>, <tex>N_b \rightarrow b</tex> и <tex>N_c \rightarrow c</tex>4 (рус.)
Теперь у нас остались только правила вида <tex>A \rightarrow BC</tex>, <tex>A \rightarrow a</tex> и, возможно, <tex>S \rightarrow \varepsilon</tex> (при условии, что <tex>S</tex> не содержится в правых частях правил). Грамматика, содержащая правила только такого вида, называется грамматикой в '''нормальной форме Хомского'''.
Заметим, что любую контекстно[[Категория: Теория формальных языков]][[Категория: Контекстно-свободную грамматику можно привести к нормальной форме Хомского. Такая форма свободные грамматики очень удобна для работы многих алгоритмов над грамматиками, например, ]][[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ|алгоритм Кока-ЯнгераКатегория: Нормальные формы КС-Касамиграмматик]]
275
правок

Навигация