390
правок
Изменения
м
Поисправлял ещё многоточия
# Найти все <tex>\varepsilon</tex>-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
# Перебираем правила грамматики <tex>\Gamma</tex>. Если найдено правило <tex>A \rightarrow C_1C_2 \ldots .C_k</tex>, для которого верно, что каждый <tex>C_i</tex> принадлежит множеству, то добавить <tex>A</tex> в множество.
# Если на шаге 2 множество изменилось, то повторить шаг 2.
Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>\varepsilon</tex>-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все <tex>\varepsilon</tex>-порождающие нетерминалы.
Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило <tex>B \rightarrow C_1C_2 \ldots .C_k</tex>, где каждый нетерминал <tex>C_i</tex> {{---}} <tex>\varepsilon</tex>-порождающий. Каждый <tex>C_i</tex> входит в множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.
}}
