Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
== Постановка задачи ==Дана [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|контекстно-свободная грамматика]]. Необходимо удалить из неё все <tex>\varepsilon</tex>-правила. == Основные Используемые определения ==
{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами'''.
== Алгоритм удаления ε-правил из грамматики ==
# Рассмотрим правила вида (*) <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex>, где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы. Добавить все возможные правила вида (*), в которых либо присутствует, либо отсутствует <tex>B_j\; (1 \le j \le k)</tex>.
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P</tex>.
# Если в исходной грамматике <tex>G</tex> выводилось пустое слово <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правила <tex>S' \rightarrow S|\varepsilon</tex>.
{{Теорема
|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G) \setminus \mathcal {f}\varepsilon \mathcal {g}</tex>.
Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>.
}}
== Алгоритм поиска ε-порождающих нетерминалов ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>.<br/>
'''Выход:''' множество <tex>\varepsilon</tex>-порождающих нетерминалов.
# Пусть <tex>N_{\varepsilon}</tex> — множество <tex>\varepsilon</tex>-порождающих нетерминалов. Добавить все нетерминалы, из которых непосредственно можно вывести <tex>\varepsilon</tex>, в множество <tex>N_{\varepsilon}</tex>.
# Если найдено правило <tex>A \rightarrow C_1C_2...C_k</tex>, для которого верно, что каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал, то добавить <tex>A</tex> в множество <tex>N_{\varepsilon}</tex>.
# Если на шаге 2 множество <tex>N_{\varepsilon}</tex> изменилось, то повторить шаг 2.
{{Теорема
|statement = Нетерминал <tex>A</tex> является <tex>\varepsilon</tex>-порождающим тогда и только тогда, если выполнено одно из следующих условий:
# в грамматике <tex>G</tex> есть правило <tex>A \rightarrow \varepsilon</tex>;
# в грамматике <tex>G</tex> есть правило <tex>A \rightarrow C_1C_2...C_k</tex>, где каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.
|proof =
Индукция по длине кратчайшего порождения <tex>A \Rightarrow^* \varepsilon</tex>.
'''База.''' <tex>A \Rightarrow \varepsilon</tex>, то есть в грамматике имеется правило <tex>A \rightarrow\varepsilon</tex>. Следовательно, <tex>A</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.
'''Переход.''' Пусть <tex>A \Rightarrow^* \varepsilon</tex> за <tex>n</tex> шагов. Тогда первый шаг порождения <tex>A \rightarrow C_1C_2...C_k</tex>, где <tex>C_i \Rightarrow^* \varepsilon</tex> за менее, чем <tex>n</tex> шагов. По индукционному предположению каждый нетерминал <tex>C_i</tex> обнаруживается как <tex>\varepsilon</tex>-порождающий. Тогда нетерминал <tex>A</tex> — <tex>\varepsilon</tex>-порождающий.
}}
== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
[[Категория: Теория формальных языков]]
