Бюрократы, editor, Администраторы
422
правки
Изменения
→Алгоритм поиска ε-порождающих нетерминалов
Индукция по длине кратчайшего порождения <tex>A \Rightarrow^* \varepsilon</tex>. Если длина кратчайшего порождения равна <tex>p</tex>, то в множестве <tex>\varepsilon</tex>-порождающих нетерминалов содержатся все нетерминалы, из которых можно вывести пустое слово <tex>\varepsilon</tex> за менее, чем <tex>p</tex> шагов.
'''База.''' <tex>A \Rightarrow \varepsilon</tex>, то есть в грамматике имеется правило <tex>A \rightarrow\varepsilon</tex>. Следовательно, <tex>A</tex> будет добавлен в множество <tex>\varepsilon</tex>-порождающих нетерминалов на первом шаге 1 алгоритма.
'''Переход.''' Пусть <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. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.
}}
