177
правок
Изменения
м
→Идея алгоритма
Введем функцию <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>)
'''return''' left
'''if''' isLeftType(<tex>N_i</tex>) && '''and''' !isRightType(<tex>N_i</tex>)
'''return''' right
'''if''' (isLeftType(<tex>N_i</tex>) && '''and''' isRightType(<tex>N_i</tex>)
'''return''' self
'''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>, т.к в противном случае грамматика будет самоприменима.
