205
правок
Изменения
м
→Поиск ε-порождающих нетерминалов
|statement = Нетерминал <tex>A</tex> является <tex>\varepsilon</tex>-порождающим тогда и только тогда, когда вышеприведенный алгоритм идентифицирует <tex>A</tex> как <tex>\varepsilon</tex>-порождающий.
|proof = Индукция по длине кратчайшего порождения <tex>A \Rightarrow^*\varepsilon</tex>
:''База.'' <tex>A \Rightarrow^*\varepsilon</tex> за один шаг, то есть <tex>A \rightarrow\varepsilon</tex>. <tex>\varepsilon</tex>-порождающий нетерминал <tex>A</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>-порождающий.
}}
