Cross product of incomplete DFA's

Question

I am trying to do a cross product between two DFA's but they are both incomplete DFA's.

The following image is the answer I came up with for the intersection of cross product between two incomplete DFA's. The alphabet is {a,b,c,d,e}.

Is it correct or does the fact that they are incomplete change everything?

Answer 1

The fact that they're incomplete does make your job different if you are constructing the cross product to find the union; however, for the intersection you can still use this basic approach. But, you made some errors:

Let's start in the top left, and look at all the transitions out of the state A1:

First, you have a state transition labeled c from state A1 to state A2. However, that's incorrect because there is no transition from A to A in the top DFA that's labeled with c. Then, you have a transition labeled a that goes from state A1 to itself. This is also incorrect because there's no transition from state 1 to anything labeled a. Likewise, there's no transition out from state 1 labeled b so that also invalidates your transition from A1 to B1.

When working with incomplete DFAs and making a cross-product like this, you'll only have outgoing edges for a state (p,q) when there's a letter that both state p and state q have outgoing edges for.

Therefore, there are no transitions out of the start state. At this point, we can stop working because with no transitions out of the start state, there's no point - the resulting DFA matches nothing.

Another possibility of how to approach this is to first make both DFAs complete by adding a non-accepting state (I call this state ∅). This state should have an edge going to it from every state for every letter for which there isn't already a different outgoing edge. For example, in the first DFA there would be an edge from A to ∅ for c, d, and e. Also, there should be an edge from ∅ to ∅ for every letter. Now both DFAs are complete.

When you do this, you end up with edges out of A1 going to: A∅ for a, B∅ for b, ∅1 for c, and ∅∅ for d and e. The rest is left as an exercise, but if you draw it out completely you'll discover again that there's no path from A1 to any accepting state.

Making both DFAs complete first is in fact what you need to do if you're constructing the cross-product to find the union - with the intersection it's permissible to simply throw away any state involving ∅ in either DFA since reaching ∅ means that you'll never reach an accepting state, but with the union you need to keep them because some states involving ∅ may be accepting states of the cross-product. (You can still throw away the state ∅∅ and any edge to that)