177
правок
Изменения
→Идея алгоритма
Заметим, что <tex> \forall i </tex> <tex>getTheTypeOfMutualRecursiveSet(N_i) \neq self </tex>, т.к в противном случае грамматика будет самоприменима.
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
# символ Символ алфавит или <tex> \varepsilon </tex> {{---}} добавляем новое правило в автомат;# нерекурсивный Нерекурсивный нетерминал {{---}} запускаемся от всех правых частей правил, который терминал порождает;# рекурсивный Рекурсивный нетерминал {{---}} в зависимости от типа рекурсивного нетерминала, продолжаем рекурсию (будет ясно из пседокода).
===Псевдокод===
