1
$\begingroup$

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 ?

$\endgroup$
  • $\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
1
$\begingroup$

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.

automata

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.