177
правок
Изменения
→Идея алгоритма
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]</tex>
Введем функцию <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i): P \rightarrow \{left, right, self, cycle\} </tex>:
'''function''' getTheTypeOfMutualRecursiveSet(<tex>N_i</tex>):
'''if''' !isLeftType(<tex>N_i</tex>) '''and''' isRightType(<tex>N_i</tex>)
'''if''' !isLeftType(<tex>N_i</tex>) '''and''' !isRightType(<tex>N_i</tex>)
'''return''' cyclic
Заметим, что <tex> \forall i </tex> <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) \neq self </tex>, т.к в противном случае грамматика будет самоприменима.
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
# Символ алфавит или <tex> \varepsilon </tex> {{---}} добавляем новое правило в автомат;
