171
правка
Изменения
Нет описания правки
return true
== Включение ==
Регулярный язык <tex>L_{1}</tex> '''входит (включается)''' в регулярный язык <tex>L_{2}</tex>, если любое слово, принадлежащее <tex>L_{1}</tex>, принадлежит <tex>L_{2}</tex>.
=== Алгоритм проверки на включение ===
Алгоритм проверки <tex>L_{1}</tex> на включение в <tex>L_{2}</tex> идентичен алгоритму проверки их совпадения, кроме одной особенности. Могут существовать слова из <tex>L_{2}</tex>, не входящие в <tex>L_{1}</tex>, поэтому существование пар <tex>\langle v \in L_{1}, u \in L_{2} \rangle : eq(v, u) == true, v \notin T_{1}, u \in T_{2}</tex>, где <tex>T_{i}</tex> - множества допускающих состояний, не нарушает факт вхождения <tex>L_{1}</tex> в <tex>L_{2}</tex>. Таким образом, <tex>L_{1}</tex> не входит в <tex>L_{2}</tex> тогда и только тогда, когда после окончания работы алгоритма, идентичного алгоритму проверки на совпадение, не существует такой пары <tex>\langle v, u \rangle</tex>, что <tex>eq(v, u)</tex> возвращает <tex>true</tex>, <tex>v \in T_{1}, u \notin T_{2}</tex>.
==== Псевдокод ====
void reverseDfs(State v):
v.canReach = true
for each State u in v.prev:
if !u.canReach:
reverseDfs(u)
void setSink(Automaton a):
State sink = new State
for each symbol c in a.alphabet:
sink.next(c) = sink
for each State v in a:
if !v.canReach:
v = sink
void bfs(Automaton a, Automaton b, boolean[][] eq)
fill(eq, false)
eq[a.start][b.start] = true
Queue q = new Queue
q.add((a.start, b.start))
while !q.isEmpty:
(v, u) = q.remove()
for each symbol c in a.alphabet: // a.alphabet == b.alphabet
v' = v.next(c)
u' = u.next(c)
if !eq[v'][u']:
eq[v'][u'] = true
q.add((v', u'))
boolean areEqual(Automaton a, Automaton b)
for each State v in a:
v.canReach = false
for each State v in a:
if v.isFinal:
reverseDfs(v)
setSink(a)
for each State v in b:
v.canReach = false
for each State v in b:
if v.isFinal:
reverseDfs(v)
setSink(b)
eq = new boolean[a.statesNumber][b.statesNumber]
bfs(a, b, eq)
for each State v in a:
for each State u in b:
if eq[v][u] && v.isFinal && !u.isFinal:
return false
return true
== Конечность языка, подсчёт числа слов ==
