Let assume that I have the following two automata A1 and A2 :

A1 A2

I have to do the intersection of the two, so I did this :

enter image description here

My question is related to the "∅". If I have two incomplete automata without dead states, and given a specific state, one automaton has a transition for one symbol but the second doesn't have it, what should I do ? For example I am in the state 13 in the transition table and I read "b", should I rather put ∅ or 4 and make it non final ?

  • $\begingroup$ Try adding a dead state to both automata and then removing all dead stares from the product automaton. $\endgroup$ – Yuval Filmus Jan 13 at 21:34
  • $\begingroup$ I did it and I found the same result. Does this mean that it is acceptable to put ∅ directly when I have to deal with two incomplete automata where one has a transition but not the other ? $\endgroup$ – Spn Jan 13 at 21:46
  • 1
    $\begingroup$ Yes. In fact, it’s the only valid definition. $\endgroup$ – Yuval Filmus Jan 13 at 21:47
  • $\begingroup$ @Spn, write your own answer? $\endgroup$ – Apass.Jack Jan 16 at 15:00

To answer the question, there are two different manners to solve this.

  1. By adding a dead state whenever you have an incomplete automata. By doing so, you will no longer have to worry about what to do if one automata has a transition from a specific state but not the other.

  2. You can still do the intersection of the two without adding dead states.


In this example, if you are focusing on the state 1 and 3 with the symbol 'b' :
- From A1, you have no transition : δ(1,b) = ∅
- From A2, you have a transition : δ(3,b) = 4

Since one has a transition, but not the other, then the resulting automata will have the transition : δ(13,b) = ∅. Therefore, it is indeed acceptable to put ∅.


Your Answer

