Open andrew-johnson-4 opened 1 year ago
The theoretical logic for union is
I think this algorithm provides closure for all possible DFAs. It would be nice to avoid NFA construction for such a basic operation.
Maybe something like a(bc)*d
union (ab)*cd
union ab(cd)*
.
Update with solution: Since this is union, we don't care if one or both machines could potentially accept, so these states can be merged. Thus "backwards" transitions can move back onto the middle path and we don't care about the implication. Any accept states from either machine will be final states for the union.
The precise union of DFAs is defined simply as the union of final states + the product of transitions.
(ab)*
union aa
could yield a 3x3 dfa where:
(0,0) -> a -> (1,1)
(1,1) -> a -> (2,0)
(1,1) -> b -> (0,2)
(0,1) -> b -> (0,2)
(0,2) -> a -> (0,1)
which is still xy bounded in space and time complexity, but this bugs out with current union op.
I heard a rumor that a.union(b)
is equivalent to a.complement().intersect(b.complement()).complement()
. I think the reason it didn't work previously was because complement
is not completely correct.
The simplest union algorithm that I can think of is that a union state is either
This algorithm would still yield an O(xy) upper bound, so it is a good fallback to cover the problematic cases with back edges.
This may be bugged, the current solution seems shaky. Try union on some more complex state machines in tests.