Удаление длинных правил из грамматики

2014-02-24T11:01:32Z

5.167.251.85: длинны -> длины

{{Определение
|definition =
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]].
Правило <tex>A \rightarrow \beta </tex> называется '''длинным''', если <tex>|\beta| > 2</tex>.
}}

== Постановка задачи ==
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая длинные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую длинных правил. 
Задача удаления длинных правил из грамматики возникает при попытке её приведения к [[нормальная форма Хомского|нормальной форме Хомского]].

== Алгоритм ==
С каждым длинным правилом <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>, <tex>k > 2</tex>, <tex>a_i \in \Sigma \cup N</tex> проделаем следующее: 
#Добавим в грамматику <tex>k-2</tex> новых нетерминала <tex>B_1, B_2, \ldots B_{k-2}</tex>. 
#Добавим в грамматику <tex>k-1</tex> новое правило: 
#:<tex>A \rightarrow a_1B_1</tex>, 
#:<tex>B_1 \rightarrow a_2B_2</tex>, 
#:<tex>B_2 \rightarrow a_3B_3</tex>, 
#:<tex>\ldots </tex>, 
#:<tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex>. 
#Удалим из грамматики правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>.
=== Корректность алгоритма ===
{{Теорема
|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>
|proof=
<tex>\Rightarrow </tex> 
Покажем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. 
Пусть <tex>w \in L(\Gamma)</tex>. Рассмотрим вывод <tex>w</tex>. Если в выводе используется длинное правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>, то заменим его на последовательное применение правил <tex>A \rightarrow a_1B_1</tex>, <tex>B_1 \rightarrow a_2B_2</tex>,
<tex>B_2 \rightarrow a_3B_3</tex>, <tex>\ldots </tex>, <tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex>. Получим вывод <tex>w</tex> в <tex>\Gamma'</tex>. 
<tex>\Leftarrow </tex> 
Покажем, что <tex>L(\Gamma') \subseteq L(\Gamma)</tex>. 
Допустим, что это не так, то есть <tex>\exists w \in L(\Gamma'), w \notin L(\Gamma)</tex>. 
Рассмотрим вывод <tex>w</tex> в <tex>\Gamma' \cup \Gamma</tex>, минимальный по количеству примененных правил, отсутствующих в <tex>\Gamma</tex>. 
Найдем в этом выводе первое применение некоторого правила <tex>A \rightarrow a_1A_1, a_1 \in \Sigma \cup N</tex>, которого нет в <tex>\Gamma</tex>. В ходе алгоритма оно было получено из некоторого длинного правила <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. Применим <tex>A \rightarrow a_1 a_2 \ldots a_k</tex> вместо <tex>A \rightarrow a_1A_1</tex> и удалим в выводе все применения правил, полученных из <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>.
Получим вывод <tex>w</tex> в <tex>\Gamma \cup \Gamma'</tex>, в котором меньше применений правил, отсутствующих в <tex>\Gamma</tex>, чем в исходном. Противоречие.
}}

== Время работы алгоритма ==
Данный алгоритм работает за <tex>O(\left| \Gamma \right|)</tex> и добавляет в грамматику <tex>O(\left| \Gamma \right|)</tex> новых правил длины <tex>O(1)</tex>.

== Пример работы ==
Покажем, как описанный алгоритм будет работать на следующей грамматике: 
<tex>S \rightarrow AB</tex>, 
<tex>A \rightarrow aBcB</tex>, 
<tex>B \rightarrow def</tex>. 

Для правила <tex>A \rightarrow aBcB</tex> вводим 2 новых нетерминала <tex>A_1, A_2</tex> и 3 новых правила: 
<tex>A \rightarrow aA_1</tex>, 
<tex>A_1 \rightarrow BA_2</tex>, 
<tex>A_2 \rightarrow cB</tex>. 

Для правила <tex>B \rightarrow def</tex> вводим 1 новый нетерминал <tex>B_1</tex> и 2 новых правила: 
<tex>B \rightarrow dB_1</tex>, 
<tex>B_1 \rightarrow ef</tex>. 

В итоге полученная грамматика <tex>\Gamma'</tex> будет иметь вид: 
<tex>S \rightarrow AB</tex>, 
<tex>A \rightarrow aA_1</tex>, 
<tex>A_1 \rightarrow BA_2</tex>, 
<tex>A_2 \rightarrow cB</tex>, 
<tex>B \rightarrow dB_1</tex>, 
<tex>B_1 \rightarrow ef</tex>. 

== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Викиконспекты - Вклад участника [ru]

Удаление длинных правил из грамматики