Изменения

Перейти к: навигация, поиск

Регулярная аппроксимация КС-языков

57 байт добавлено, 21:35, 19 декабря 2016
м
Идея алгоритма
Пусть, <tex> P = \{N_1,N_2,\ldots,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </tex> дизъюнктных множеств взаимно рекурсивных нетерминалов,
<tex> N_1 \cup N_2 \cup \ldots \cup N_k = N^* \land \forall i</tex> <tex> N_i \neq \emptyset </tex>.
'''bool''' isLeftType(<tex>N_i</tex>: '''nonterminal'''):
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]</tex>
'''bool''' isRightType(<tex>N_i</tex>: '''nonterminal'''):
'''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>: '''nonterminal'''):
'''if''' !isLeftType(<tex>N_i</tex>) '''and''' isRightType(<tex>N_i</tex>)
'''return''' left
177
правок

Навигация