HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Should two DFAs be complete before making an intersection of them?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
intersectiontwodfascompleteshouldbeforemakingthem

Problem

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

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?

Solution

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.

Context

StackExchange Computer Science Q#65037, answer score: 9

Revisions (0)

No revisions yet.