Изменения
→Алгоритм поиска ε-порождающих нетерминалов
'''Выход:''' множество <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>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 (рус.)
[[Категория: Теория формальных языков]]
