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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример работы)
Строка 24: Строка 24:
 
|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>. <br>
 
<tex>\Leftarrow </tex> <br>
 
<tex>\Leftarrow </tex> <br>
Покажем, что <tex>L(\Gamma') \subset L(\Gamma)</tex>. <br>
+
Покажем, что <tex>L(\Gamma') \subseteq L(\Gamma)</tex>. <br>
 
Допустим, что это не так, то есть <tex>\exists w \in L(\Gamma'), w \notin L(\Gamma)</tex>. <br>  
 
Допустим, что это не так, то есть <tex>\exists w \in L(\Gamma'), w \notin L(\Gamma)</tex>. <br>  
 
Рассмотрим вывод <tex>w</tex> в <tex>\Gamma' \cup \Gamma</tex>, минимальный по количеству примененных правил, отсутствующих в <tex>\Gamma</tex>. <br>
 
Рассмотрим вывод <tex>w</tex> в <tex>\Gamma' \cup \Gamma</tex>, минимальный по количеству примененных правил, отсутствующих в <tex>\Gamma</tex>. <br>

Версия 16:35, 24 января 2012

Определение:
Пусть [math]\Gamma[/math]контекстно-свободная грамматика. Правило [math]A \rightarrow \beta [/math] называется длинным, если [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] проделаем следующее:

  1. Добавим в грамматику [math]k-2[/math] новых нетерминала [math]B_1, B_2, \ldots B_{k-2}[/math].
  2. Добавим в грамматику [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].
  3. Удалим из грамматики правило [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]S \rightarrow AB[/math],
[math]A \rightarrow aBcB[/math],
[math]B \rightarrow def[/math].

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

Для правила [math]B \rightarrow def[/math] вводим 1 новый нетерминал [math]B_1[/math] и 2 новых правила:
[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].