Изменения
→Идея алгоритма
Пусть, <tex> P = \{N_1,N_2,...,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </tex> дизъюнктных множеств взаимно рекурсивных терминалов,
<tex> N_1 \cup N_2 \cup ... \cup N_k = N^* \land \forall i N_i \neq \emptyset </tex>.
Ввведем функцию <tex> recursivegetTheTypeOfMutualRecursiveSet(N_i): P \rightarrow \{left, right, self, cycle\} </tex>:
'''function''' IsLeftType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]</tex>
'''function''' recursive getTheTypeOfMutualRecursiveSet (<tex>N_i</tex>): '''if''' !IsLeftType(<tex>N_i</tex>) && IsRihtTypeIsRightType(<tex>N_i</tex>)
return left;
'''if''' IsLeftType(<tex>N_i</tex>) && !IsRihtTypeIsRightType(<tex>N_i</tex>)
return right;
'''if''' (IsLeftType(<tex>N_i</tex>) && IsRihtTypeIsRightType(<tex>N_i</tex>)
return self;
'''if''' !IsLeftType(<tex>N_i</tex>) && !IsRihtTypeIsRightType(<tex>N_i</tex>)
return cyclic;
Заметим, что <tex> \forall i </tex> <tex>recursivegetTheTypeOfMutualRecursiveSet(N_i) \neq self </tex>, т.к грамматика не самоприменима.<br \>
В основе алгоритма будет рекурсивный обход грамматики во все стороны. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
# символ алфавит или <tex> \varepsilon </tex> {{---}} добавляем новое правило в автомат
