in Theory of Computation
545 views
1 vote
1 vote

Number of 3 state DFA with designated initial state can be constructed over the alphabet 

$\sum$ = {0,1,2} with exactly 2 final states is

  1. $3^{8}$ B)$3^{9}$  C) $3^{10}$   D) $3^{11}$

Answer is C

in Theory of Computation
545 views

4 Comments

which test series?
0
0
Having one doubt in the question. is it asking for total $DFA’s$ or total strings which can be produced?
0
0
It is asked in ACE.

I think it is asking for total DFA’s.

Your answer given below seems to be correct.
0
0
0
0

1 Answer

3 votes
3 votes

My reasoning for this question is:

As we have a $DFA$ having $3$ states with exactly two as the final states.

so to select $2$ final states from $3$ states we can select it in $^{3}\textrm{C}_{2}$ ways  so now we have $3$ $DFA’s$

The alphabet given in the question contains $3$ symbols  $({0,1,2})$

$(each$ $symbol$ $from$ $each$ $state$ $has$ $3$ $choices$ $either$ $it$ $can$ $loop$ $over$ $the$ $same$ $state$, $or$ $go$ $to$ $any$ $one$ $state$ $from$ $the$ $remaining$ $two$)

And , as it is a $DFA$ every state should have transitions for all the symbols and hence for $3$ states each having $3$ symbols . (For forming a valid String we are only taking transition on one symbol per state).

thus the choices we have for all the $3$ states and $3$ symbols will be $3^9$

and initially we had $^{3}\textrm{C}_{2}$ for selecting the final states thus total $DFA’s$ possible 

$3^9*3$

$3^{10}$

 

Related questions