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?

$\endgroup$
  • 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$ – user253751 Oct 24 '16 at 22:32
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".)

$\endgroup$
  • 1
    $\begingroup$ @JohnMayne Probably your teacher just forgot a transition in his slides. You should ask him. $\endgroup$ – adrianN Oct 24 '16 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 Oct 24 '16 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 Oct 24 '16 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 Oct 24 '16 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 Oct 24 '16 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.

$\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.