How many DFAs are possible?

Question

How many 3 state DFA's can be constructed with a designated initial final state that accepts empty language over alphabet {a,b}?

Answer 1

Answer: 189

Let us consider the three states to be 1, 2 and 3

Since, it is given "designated initial state", so let us assume the initial state to be 1

Now, we want to construct a DFA which accepts empty language which means $\varnothing$

Please note: A DFA which accepts nothing does not even accept $\varepsilon$. 

For example, below DFA has initial state as final state, so it accepts atleast $\varepsilon$. Hence it is not a DFA which accepts empty language. Empty language means nothing is accepted.

So, we cannot mark initial state as final state for our DFA. Hence, we have to choose one state as final - from state 2 or state 3. Let us choose 2 as final state.

Please note:

• Since we are given designated final state, we have to have final state, So choosing no state as final is not possible.
• Marking both 2 and 3 as final also not possible as we question says "a final state"

Now, let us decide about transitions from states.

• When state 2 is marked as final, there should be no transitions from state 1 to state 2 otherwise those strings would be accepted. Remember we want to accept nothing

         So, there would be  $3^{4}$  +  $3 * 3* 2*2$ + $3 * 3 * 2* 2 $ + $3 * 3 * 2* 2$

So, there would be  $81 + 36 + 36 + 36$ which is $189$ possibilities

So total 189 DFAs possible

Special thanks to Ahwan for pointing out my errors :)

Comments

Agree. I really need to practice reading and understanding carefully :(

Edited :)

---

Still I do not know if its the right answer. Lets see if some one comes with a better argument.

---

In the first diagram, the final state is ‘2’. But there can’t be any transition from state 3 to state 2 right? Otherwise the string would be accepted. Or am I missing something?

Answer 2

3 States . Initial & final states are designated.

Comments

In last figure which state is final ?

---

Initial is always 1...Final is always 3 ... (Designated)  I took 1 as initial.. 3 as final...  I cant change them.

Answer 3

Answer:144

	a	b
->x	x/y	x/y
y	x/y	x/y
*z	x/y/z	x/y/z

2*2*2*2*3*3=144

Since we have to accept empty language,

Therefore  from x and y , we should not have any transition to z.