Изменения

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

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

4 байта добавлено, 16:35, 24 января 2012
Нет описания правки
|proof=
<tex>\Rightarrow </tex> <br>
Покажем, что <tex>L(\Gamma) \subset 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>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>L(\Gamma') \subset subseteq 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>
142
правки

Навигация