+ # Reverse an automaton in place
+ fun reverse
+ do
+ for s in states do
+ var tmp = s.ins
+ s.ins = s.outs
+ s.outs = tmp
+ for t in s.outs do
+ var tmp2 = t.from
+ t.from = t.to
+ t.to = tmp2
+ end
+ end
+ var st = start
+ if accept.length == 1 then
+ start = accept.first
+ else
+ var st2 = new State
+ start = st2
+ states.add(st2)
+
+ for s in accept do
+ st2.add_trans(s, null)
+ end
+ end
+ accept.clear
+ accept.add(st)
+ end
+
+ # Remove states (and transitions) that does not reach an accept state
+ fun trim
+ do
+ # Good states are those we want to keep
+ var goods = new HashSet[State]
+ goods.add_all(accept)
+
+ var todo = accept.to_a
+
+ # Propagate goodness
+ while not todo.is_empty do
+ var s = todo.pop
+ for t in s.ins do
+ var s2 = t.from
+ if goods.has(s2) then continue
+ goods.add(s2)
+ todo.add(s2)
+ end
+ end
+
+ # What are the bad state then?
+ var bads = new Array[State]
+ for s in states do
+ if not goods.has(s) then bads.add(s)
+ end
+
+ # Remove their transitions and tags
+ for s in bads do
+ for t in s.ins.to_a do t.delete
+ for t in s.outs.to_a do t.delete
+ if tags.has_key(s) then
+ for t in tags[s] do retrotags[t].remove(s)
+ tags.keys.remove(s)
+ end
+ end
+
+ # Keep only the good stuff
+ states.clear
+ states.add_all(goods)
+ states.add(start)
+ end
+
+ # Generate a minimal DFA
+ # REQUIRE: self is a DFA
+ fun to_minimal_dfa: Automaton
+ do
+ assert_valid
+
+ trim
+
+ # Graph of known distinct states.
+ var distincts = new HashMap[State, Set[State]]
+ for s in states do
+ distincts[s] = new HashSet[State]
+ end
+
+ # split accept states.
+ # An accept state is distinct with a non accept state.
+ for s1 in accept do
+ for s2 in states do
+ if distincts[s1].has(s2) then continue
+ if not accept.has(s2) then
+ distincts[s1].add(s2)
+ distincts[s2].add(s1)
+ continue
+ end
+ if tags.get_or_null(s1) != tags.get_or_null(s2) then
+ distincts[s1].add(s2)
+ distincts[s2].add(s1)
+ continue
+ end
+ end
+ end
+
+ # Fixed point algorithm.
+ # * Get 2 states s1 and s2 not yet distinguished.
+ # * Get a symbol w.
+ # * If s1.trans(w) and s2.trans(w) are distinguished, then
+ # distinguish s1 and s2.
+ var changed = true
+ var ints = new Array[Int] # List of symbols to check
+ while changed do
+ changed = false
+ for s1 in states do for s2 in states do
+ if distincts[s1].has(s2) then continue
+
+ # The transitions use intervals. Therefore, for the states s1 and s2,
+ # we need to check only the meaningful symbols. They are the `first`
+ # symbol of each interval and the first one after the interval (`last+1`).
+ ints.clear
+ # Check only `s1`; `s2` will be checked later when s1 and s2 are switched.
+ for t in s1.outs do
+ var sym = t.symbol
+ assert sym != null
+ ints.add sym.first
+ var l = sym.last
+ if l != null then ints.add l + 1
+ end
+
+ # Check each symbol
+ for i in ints do
+ var ds1 = s1.trans(i)
+ var ds2 = s2.trans(i)
+ if ds1 == ds2 then continue
+ if ds1 != null and ds2 != null and not distincts[ds1].has(ds2) then continue
+ distincts[s1].add(s2)
+ distincts[s2].add(s1)
+ changed = true
+ break
+ end
+ end
+ end
+
+ # We need to unify not-distinguished states.
+ # Just add an epsilon-transition and DFAize the automaton.
+ for s1 in states do for s2 in states do
+ if distincts[s1].has(s2) then continue
+ s1.add_trans(s2, null)
+ end
+
+ return to_dfa
+ end
+
+ # Assert that `self` is a valid automaton or abort
+ fun assert_valid
+ do
+ assert states.has(start)
+ assert states.has_all(accept)
+ for s in states do
+ for t in s.outs do assert states.has(t.to)
+ for t in s.ins do assert states.has(t.from)
+ end
+ assert states.has_all(tags.keys)
+ for t, ss in retrotags do
+ assert states.has_all(ss)
+ end
+ end
+
+ # Produce a graphviz string from the automatom
+ #
+ # Set `merge_transitions = false` to generate one edge by transition (default true).
+ fun to_dot(merge_transitions: nullable Bool): Writable