Удаление длинных правил из грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 20 промежуточных версий 10 участников)
Строка 2: Строка 2:
 
|definition =
 
|definition =
 
Пусть  <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]].
 
Пусть  <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]].
Правило <tex>A \rightarrow \beta </tex> называется '''длинным''' если <tex>|\beta| > 2</tex>
+
Правило <tex>A \rightarrow \beta </tex> называется '''длинным''' (англ. ''long rule''), если <tex>|\beta| > 2</tex>.
 
}}  
 
}}  
  
== Постановка задачи ==
+
{{Задача
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая длинные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую длинных правил. <br>
+
|definition=
Задача удаления длинных правил из грамматики возникает при попытке ее приведения к [[нормальная форма Хомского|нормальной форме Хомского]].
+
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая длинные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую длинных правил. <br>
 +
Задача удаления длинных правил из грамматики возникает при попытке её приведения к [[нормальная форма Хомского|нормальной форме Хомского]].
 +
}}
 +
 
 +
 
 
== Алгоритм ==
 
== Алгоритм ==
С каждым длинным правилом <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>, <tex>k > 2</tex>, <tex>a_i \in \Sigma \cup N</tex> проделаем следующее: <br>
+
С каждым длинным правилом <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> <br>
+
* Добавим в грамматику <tex>k-2</tex> новых нетерминала <tex>B_1, B_2, \ldots B_{k-2}</tex>.
Добавим в грамматику <tex>k-1</tex> новое правило: <br>
+
* Добавим в грамматику <tex>k-1</tex> новое правило:  
<tex>A \rightarrow a_1B_1</tex> <br>
+
*;<tex>A \rightarrow a_1B_1</tex>
<tex>B_1 \rightarrow a_2B_2</tex> <br>
+
*;<tex>B_1 \rightarrow a_2B_2</tex>  
<tex>B_2 \rightarrow a_3B_3</tex> <br>
+
*;<tex>B_2 \rightarrow a_3B_3</tex>
<tex>\ldots </tex> <br>
+
*;<tex>\ldots </tex>
<tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex> <br>
+
*;<tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex>
Удалим из грамматики правило <tex>A \rightarrow a_1 a_2 \ldots 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>
+
|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>
 
|proof=
 
|proof=
 
<tex>\Rightarrow </tex> <br>
 
<tex>\Rightarrow </tex> <br>
Покажем, что <tex>L(\Gamma) \subset L(\Gamma')</tex> <br>
+
Покажем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. <br>
 
Пусть <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>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> <br>
+
<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> <br>
 
<tex>\Leftarrow </tex> <br>
Покажем, что <tex>L(\Gamma') \subset L(\Gamma)</tex> <br>
+
Покажем, что <tex>L(\Gamma') \subseteq L(\Gamma)</tex>.
Допустим, что это не так, и <tex>\exists w \in L(\Gamma'), w \notin L(\Gamma)</tex>. <br>
+
Допустим, что это не так, то есть <tex>\exists w \in L(\Gamma'), w \notin L(\Gamma)</tex>.  
Рассмотрим вывод <tex>w</tex> в <tex>\Gamma' \cup \Gamma</tex>, минимальный по количеству примененных правил, отсутствующих в <tex>\Gamma</tex>. <br>
+
Рассмотрим вывод <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>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>w</tex> в <tex>\Gamma \cup \Gamma'</tex>, в котором меньше применений правил, отсутствующих в <tex>\Gamma</tex>, чем в исходном. Противоречие.
 
}}
 
}}
 +
 +
== Время работы алгоритма ==
 +
Здесь будем понимать под <tex> | \Gamma | </tex> сумму длин правых частей правил. Данный алгоритм добавляет в грамматику <tex>O(\left| \Gamma \right|)</tex> новых нетерминалов, <tex>O(\left| \Gamma \right|)</tex> новых правил длины <tex>O(1)</tex> и, следовательно, работает за <tex>O(\left| \Gamma \right|)</tex>.
 +
 
== Пример работы ==
 
== Пример работы ==
Покажем, как описанный алгоритм будет работать на следующей грамматике: <br>
+
Покажем, как описанный алгоритм будет работать на следующей грамматике:  
<tex>S \rightarrow AB</tex> <br>
+
: <tex>S \rightarrow AB</tex>      
<tex>A \rightarrow aBcB</tex> <br>
+
: <tex>A \rightarrow aBcB</tex>  
<tex>B \rightarrow def</tex> <br>
+
: <tex>B \rightarrow def</tex>.
 +
 
 +
Для правила <tex>A \rightarrow aBcB</tex> вводим <tex> 2 </tex> новых нетерминала <tex>A_1, A_2</tex> и <tex> 3 </tex> новых правила:
 +
: <tex>A \rightarrow aA_1</tex>
 +
: <tex>A_1 \rightarrow BA_2</tex>
 +
: <tex>A_2 \rightarrow cB</tex>.
 +
 
 +
Для правила <tex>B \rightarrow def</tex> вводим <tex> 1 </tex> новый нетерминал <tex>B_1</tex> и <tex> 2 </tex> новых правила:
 +
: <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>.
  
Для правила <tex>A \rightarrow aBcB</tex> вводим 2 новых нетерминала <tex>A_1, A_2</tex>, и 3 новых правила: <br>
+
== См. также  ==
<tex>A \rightarrow aA_1</tex> <br>
+
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
<tex>A_1 \rightarrow BA_2</tex> <br>
+
* [[Нормальная форма Хомского]]
<tex>A_2 \rightarrow bB</tex> <br>
 
  
Для правила <tex>B \rightarrow def</tex> вводим 1 новый нетерминал <tex>B_1</tex>, и 2 новых правила: <br>
+
== Источники информации ==
<tex>B \rightarrow dB_1</tex> <br>
+
* ''Michael Sipser'' Introduction to the Theory of Computation. — PWS Publishing, 1997. — ISBN 0-534-94728-X. (с 107.)
<tex>B_1 \rightarrow ef</tex> <br>
+
* ''Michael A. Harrison'' Introduction to Formal Language Theory. — Addison-Wesley, 1978. — ISBN 978-0201029550. (с 103.)
 +
* [[wikipedia:en:Chomsky_normal_form#Converting a grammar to Chomsky Normal Form | Wikipedia {{---}} Chomsky normal form]]
  
В итоге, полученная грамматика <tex>\Gamma'</tex> будет иметь вид: <br>
+
[[Категория: Теория формальных языков]]
<tex>S \rightarrow AB</tex> <br>
+
[[Категория: Контекстно-свободные грамматики]]
<tex>A \rightarrow aA_1</tex> <br>
+
[[Категория: Нормальные формы КС-грамматик]]
<tex>A_1 \rightarrow BA_2</tex> <br>
 
<tex>A_2 \rightarrow bB</tex> <br>
 
<tex>B \rightarrow dB_1</tex> <br>
 
<tex>B_1 \rightarrow ef</tex> <br>
 

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

Определение:
Пусть [math]\Gamma[/math]контекстно-свободная грамматика. Правило [math]A \rightarrow \beta [/math] называется длинным (англ. long rule), если [math]|\beta| \gt 2[/math].


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


Алгоритм

С каждым длинным правилом [math]A \rightarrow a_1 a_2 \ldots a_k[/math], [math]k \gt 2[/math], [math]a_i \in \Sigma \cup N[/math] проделаем следующее:

  • Добавим в грамматику [math]k-2[/math] новых нетерминала [math]B_1, B_2, \ldots B_{k-2}[/math].
  • Добавим в грамматику [math]k-1[/math] новое правило:
    [math]A \rightarrow a_1B_1[/math]
    [math]B_1 \rightarrow a_2B_2[/math]
    [math]B_2 \rightarrow a_3B_3[/math]
    [math]\ldots [/math]
    [math]B_{k-2} \rightarrow a_{k-1}a_{k}[/math]
  • Удалим из грамматики правило [math]A \rightarrow a_1 a_2 \ldots a_k[/math].

Корректность алгоритма

Теорема:
Пусть [math]\Gamma[/math]контекстно-свободная грамматика. [math]\Gamma'[/math] — грамматика, полученная в результате применения алгоритма к [math]\Gamma[/math]. Тогда [math]L(\Gamma) = L(\Gamma').[/math]
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow [/math]
Покажем, что [math]L(\Gamma) \subseteq L(\Gamma')[/math].
Пусть [math]w \in L(\Gamma)[/math]. Рассмотрим вывод [math]w[/math]. Если в выводе используется длинное правило [math]A \rightarrow a_1 a_2 \ldots a_k[/math], то заменим его на последовательное применение правил [math]A \rightarrow a_1B_1[/math], [math]B_1 \rightarrow a_2B_2[/math], [math]B_2 \rightarrow a_3B_3[/math], [math]\ldots [/math], [math]B_{k-2} \rightarrow a_{k-1}a_{k}[/math]. Получим вывод [math]w[/math] в [math]\Gamma'[/math].

[math]\Leftarrow [/math]
Покажем, что [math]L(\Gamma') \subseteq L(\Gamma)[/math]. Допустим, что это не так, то есть [math]\exists w \in L(\Gamma'), w \notin L(\Gamma)[/math]. Рассмотрим вывод [math]w[/math] в [math]\Gamma' \cup \Gamma[/math], минимальный по количеству примененных правил, отсутствующих в [math]\Gamma[/math]. Найдем в этом выводе первое применение некоторого правила [math]A \rightarrow a_1A_1, a_1 \in \Sigma \cup N[/math], которого нет в [math]\Gamma[/math]. В ходе алгоритма оно было получено из некоторого длинного правила [math]A \rightarrow a_1 a_2 \ldots a_k[/math]. Применим [math]A \rightarrow a_1 a_2 \ldots a_k[/math] вместо [math]A \rightarrow a_1A_1[/math] и удалим в выводе все применения правил, полученных из [math]A \rightarrow a_1 a_2 \ldots a_k[/math].

Получим вывод [math]w[/math] в [math]\Gamma \cup \Gamma'[/math], в котором меньше применений правил, отсутствующих в [math]\Gamma[/math], чем в исходном. Противоречие.
[math]\triangleleft[/math]

Время работы алгоритма

Здесь будем понимать под [math] | \Gamma | [/math] сумму длин правых частей правил. Данный алгоритм добавляет в грамматику [math]O(\left| \Gamma \right|)[/math] новых нетерминалов, [math]O(\left| \Gamma \right|)[/math] новых правил длины [math]O(1)[/math] и, следовательно, работает за [math]O(\left| \Gamma \right|)[/math].

Пример работы

Покажем, как описанный алгоритм будет работать на следующей грамматике:

[math]S \rightarrow AB[/math]
[math]A \rightarrow aBcB[/math]
[math]B \rightarrow def[/math].

Для правила [math]A \rightarrow aBcB[/math] вводим [math] 2 [/math] новых нетерминала [math]A_1, A_2[/math] и [math] 3 [/math] новых правила:

[math]A \rightarrow aA_1[/math]
[math]A_1 \rightarrow BA_2[/math]
[math]A_2 \rightarrow cB[/math].

Для правила [math]B \rightarrow def[/math] вводим [math] 1 [/math] новый нетерминал [math]B_1[/math] и [math] 2 [/math] новых правила:

[math]B \rightarrow dB_1[/math]
[math]B_1 \rightarrow ef[/math].

В итоге полученная грамматика [math]\Gamma'[/math] будет иметь вид:

[math]S \rightarrow AB[/math]
[math]A \rightarrow aA_1[/math]
[math]A_1 \rightarrow BA_2[/math]
[math]A_2 \rightarrow cB[/math]
[math]B \rightarrow dB_1[/math]
[math]B_1 \rightarrow ef[/math].

См. также

Источники информации

  • Michael Sipser Introduction to the Theory of Computation. — PWS Publishing, 1997. — ISBN 0-534-94728-X. (с 107.)
  • Michael A. Harrison Introduction to Formal Language Theory. — Addison-Wesley, 1978. — ISBN 978-0201029550. (с 103.)
  • Wikipedia — Chomsky normal form