TOC

Question

Let Q0 and Q1 are two states and Q0 is always the inital state over the alphabet {a,b} ,then possible number of DF'a with two states will be

1)32

2)64

3)80

4)120

Answer 1

Option 2.

Considering Q0 to be initial state, there can be four types of DFA

1: Q0 is initial

2. Q0 is initial and final

3. Q0 is initial and Q1 is final

4. Q0 is initial and both Q0,Q1 are final

All four cases will have 16 sub-types each. Since we have two input alphabets, a state can have two transition for an alphabet, either to itself or to the other one.

e.g Q0 on 'a' can either stay in Q0 or go to Q1, similarly Q0 on 'b' can either go to Q1 or stay in Q0.

So we have 4 possiblities of state transition for each state, Since we have 2 states, total possiblities is 4^2 = 16

Now we have 4 types of DFA with 16 possiblities in each DFA, therefore total DFA possible = 4*16 = 64.