6
$\begingroup$

In the slides given by my teacher, the third automaton is the product of the first two:

Three DFAs

I tried to do the product myself by doing the transition table of both automata at the same time. I got stuck when I realised that the second automaton has no transition from state $2$ with $a$ as input symbol, thus the automaton should halt at that moment. In the third automaton, I can see there is no transition with input symbol $a$ in any of the states that have $2$ in (sorry for the bad expression, don't know how else to say it).

So when doing the transition table of the two automata, if there is no transition, should I just ignore it like in the 3rd automaton? Or would it be wise to complete the automaton?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ If you allow for incomplete automata then that is indeed how it should work. The transition "a" is forbidden in states 02 and 12. $\endgroup$
    – Criticizing Israel not allowed
    Commented Oct 24, 2016 at 22:32

2 Answers 2

Reset to default
7
$\begingroup$

By definition, a deterministic finite-state automaton $(Q,\Sigma,\delta,q_0,F)$ must have a total transition function: For every $q \in Q$ and $a \in \Sigma$, $\delta(q,a)$ must be defined.

Automaton no. 2 is not well-defined and for this reason it makes no sense to apply the product construction to the two automata given in your question.

(A note on grammar: The singular form is automaton, the plural is automata – we cannot speak of "an automata" or "two automatas".)

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ @JohnMayne Probably your teacher just forgot a transition in his slides. You should ask him. $\endgroup$
    – adrianN
    Commented Oct 24, 2016 at 8:53
  • 8
    $\begingroup$ "By definition" -- not every definition. You can reasonably leave out transitions, provided you adapt the semantics accordingly. (cc @JohnMayne) $\endgroup$
    – Raphael
    Commented Oct 24, 2016 at 11:25
  • 2
    $\begingroup$ I'd just call the second automaton non-deterministic and act accordingly. That is, a missing transition is a non-match. $\endgroup$
    – John Dvorak
    Commented Oct 24, 2016 at 12:48
  • 1
    $\begingroup$ I'm curious as to how you would make 2 deterministic. Would you just add a transition on 'a' from state 2 to a new non-accepting state that transitions on 'a' and 'b' back to itself? $\endgroup$
    – Shufflepants
    Commented Oct 24, 2016 at 15:40
  • 6
    $\begingroup$ It's a commom notational shortcut to ommit dead-end states. They are obviously there, if this is the convention adopted. This is a pointless argument. $\endgroup$
    – André Souza Lemos
    Commented Oct 24, 2016 at 18:52
9
$\begingroup$

So when doing the transition table of the two automata, if there is no transition, should I just ignore it like in the 3rd automaton?

If there is no transition in one of the automata, then that one won't accept the input word. Therefore, the automaton for the intersection should not accept either; not having a transition is one way to make sure of that.

Improve this answer
$\endgroup$

Your Answer

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

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