205
правок
Изменения
м
# Построить граф <tex>Gr = \langle V = N, E = \mathcal {f} (A, B) | A \rightarrow \alpha B \beta \mathcal {g}\rangle</tex>, где <tex>\alpha, \beta</tex> состоят из нетерминалов.
→Поиск ε-порождающих нетерминалов
''Схема алгоритма:''
# Пометить все нетерминалы, из которых непосредственно можно вывести <tex>\mathcal {f} \varepsilon \mathcal {g}</tex>, как <tex>\varepsilon</tex>-порождающие.
# Обойти граф Если для правила <tex>GrA \rightarrow C_1C_2...C_k</tex> в глубину. Если для нетерминала верно, что каждый <tex>AC_i</tex> верно, что все его соседи — <tex>\varepsilon</tex>-порождающие нетерминалы, и при этом эти нетерминалы принадлежат одному правилупорождающий нетерминал, то пометить нетерминал <tex>A</tex>, как <tex>\varepsilon</tex>-порождающий.
{{Теорема
