205
правок
Изменения
м
→Поиск ε-порождающих нетерминалов
:2) Если <tex>B \rightarrow C_1C_2...C_k</tex> — правило грамматики <tex>G</tex>, где каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал, то <tex>B</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.
{{Теорема|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> обнаруживается алгоритмом. }}
=== Бла-бла ===
