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 ?

Improve this question
$\endgroup$
4
  • $\begingroup$ Try adding a dead state to both automata and then removing all dead stares from the product automaton. $\endgroup$
    – Yuval Filmus
    Jan 13, 2019 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, 2019 at 21:46
  • 1
    $\begingroup$ Yes. In fact, it’s the only valid definition. $\endgroup$
    – Yuval Filmus
    Jan 13, 2019 at 21:47
  • $\begingroup$ @Spn, write your own answer? $\endgroup$
    – John L.
    Jan 16, 2019 at 15:00

1 Answer 1

Reset to default
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 ∅.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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