Check for bug in .union for transitions that go backwards

[andrew-johnson-4]

This may be bugged, the current solution seems shaky. Try union on some more complex state machines in tests.

[andrew-johnson-4]

The theoretical logic for union is

• If a sequence of input could be in both state machines, stay in the middle
• If a sequence falls off of the intersection, but is still on track for one state machine, then continue to follow the sequence of that machine
• otherwise reject

I think this algorithm provides closure for all possible DFAs. It would be nice to avoid NFA construction for such a basic operation.

[andrew-johnson-4]

Maybe something like a(bc)*d union (ab)*cd union ab(cd)*.

[andrew-johnson-4]

#12

[andrew-johnson-4]

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.

[andrew-johnson-4]

The precise union of DFAs is defined simply as the union of final states + the product of transitions.

[andrew-johnson-4]

(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.

[andrew-johnson-4]

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.

[andrew-johnson-4]

The simplest union algorithm that I can think of is that a union state is either

• rejected
• on the left
• on the right
• on the intersection

This algorithm would still yield an O(xy) upper bound, so it is a good fallback to cover the problematic cases with back edges.