275
правок
Изменения
м
==Несколько определений==
Если <tex> A \rightarrow B_1При таком порядке действий размеры грамматики возрастают полиномиально....B_n </tex>, где все <tex> B_i </tex> обнуляемые, то <tex> A </tex> тоже обнуляемый.}}
{{Определение|definition=Пара нетерминалов После удалении длинных правил из каждого правила длины <tex> A k \geqslant 3 </tex> и могло появиться <tex> B k-1 </tex> называется '''узловой'''новых правил, если <tex> A \Rightarrow^* B </tex>причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.
Если Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex> (A, B) где <tex> n </tex> {{---}} узловая парачисло нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, а выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна <tex> B \rightarrow C k </tex>, то размер грамматики возрастет не больше, чем на <tex> (A, C) k \cdot n^2 </tex> тоже узловая пара.}}
{{ОпределениеНаконец, на последнем шаге может произойти добавление не более, чем <tex>|\Sigma|definition=Правило </tex> (<tex> A \rightarrow w Sigma</tex> называется '''смешанным'''{{---}} алфавит грамматики) новых правил, если причем все они будут длины <tex> w 1</tex> содержит хотя бы один терминал и хотя бы один нетерминал.
{{Теорема|statement=Любую контекстно-свободную грамматику можно преобразовать в нормальную форму Хомского= См.|proofтакже ==Рассмотрим * [[Контекстно-свободные грамматикисвободные_грамматики, вывод_вывод, лево_лево- и правосторонний вывод_и_правосторонний_вывод, дерево разбора_дерево_разбора|контекстноКонтекстно-свободную грамматикусвободные грамматики]]* [[Нормальная_форма_Куроды | Нормальная форма Куроды]]* [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах | Приведение грамматики к ослабленной нормальной форме Грейбах]] <tex> \Gamma </tex>. Для преобразования ее в нормальную форму Хомского необходимо выполнить 5 шагов. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.
# Создание новой стартовой вершины.==Источники информации==#* [[wikipedia:en: Создадим новую стартовую вершину <tex> S_0 </tex> с новым правилом <tex> S_0 \rightarrow S </tex>, где <tex> S </tex> Chomsky normal form | Wikipedia {{---}} старая стартовая вершина. Добавим в <tex> \Gamma_1 </tex> новую вершину, правило и <tex> \Gamma </tex>.Chomsky normal form]]# Удаление <tex> \varepsilon </tex>-правил* ''Хопкрофт Д.##Если <tex> A \rightarrow \varepsilon </tex>, то выкинем такое правилоМотвани Р.##Если <tex> A \rightarrow w </tex>, где <tex> w </tex> не содержит <tex> \varepsilon </tex> и обнуляемых нетерминалов, то добавим такое правило в <tex> \Gamma_2 </tex>Ульман Д.##Если <tex> A \rightarrow w </tex>, причем <tex> w </tex> содержит обнуляемые нетерминалы, то представим <tex> w </tex> '' — '''Введение в следующем виде <tex> w=w_0 N_0 w_1 N_1 ... w_{n-1} N_{n-1} w_n N_n </tex>теорию автоматов, где <tex> N_i </tex> {{---}} вхождение обнуляемого нетерминалаязыков и вычислений''', а <tex> w_i </tex> не содержит обнуляемых нетерминалов. Добавим в <tex> \Gamma_2 </tex> все правила, которые можно получить удалением всевозможных комбинаций <tex> N_i </tex> из <tex> w </tex>. Таких вариантов будет <tex> 2^n </tex>. #:Если стартовая вершина <tex> \Gamma_1 </tex> является обнуляемой, то добавим в <tex> \Gamma_2 </tex> правило <tex> S_0 \rightarrow \varepsilon </tex>.# Преобразование узловых пар.#:Для каждой узловой пары <tex> (A, B) </tex>, найдем все правила <tex> B \rightarrow w </tex>, где <tex> w </tex> {{---}} произвольная строка терминалов и нетерминалов, и добавим <tex> A \rightarrow w </tex> в <tex> \Gamma_3 </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_4 </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_4 </tex>2002. # Преобразование длинных правил— 528с.#:Для каждого правила вида <tex> A \rightarrow B_0 B_1 ... B_n </tex>, где <tex> n \ge 2 </tex>, добавим новые нетерминалы <tex> A_1, A_2, ... , A_{nISBN 5-2} </tex> и правила <tex> A \rightarrow B_1 A_1 </tex>, <tex> A_1 \rightarrow B_2 A_2 </tex>, <tex> A_2 \rightarrow B_3 A_3 </tex>, <tex> ... </tex> , <tex> A_{n8459-2} \rightarrow B_{n0261-1} B_n </tex> в <tex> \Gamma_5 </tex>4 (рус. )
Таким образом мы получили грамматику <tex> \Gamma_5 </tex> в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
}}
==Литература==[[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]]* http[[Категория://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdfНормальные формы КС-грамматик]]
→Источники информации
{{Определение
|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>O(2^{\left| \Gamma \right|})</tex>. Третье правило идет после второго, потому что после удаления <tex>\varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьего и второго, так как они могут порождать бесполезные символы.
При удалении <tex> \forall A varepsilon </tex> выполняется -правил из грамматики, содержащей правила длины <tex> (A0, A) 1</tex> {{---}} узловая параи <tex>2</tex>, размеры грамматики могли вырасти не больше, чем в <tex>3</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>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>
