Classroom notes

Question

PLease help me , i have seen the same questions in many places but didnt understand the solution .

Comments

Is answer 16? As there will not be any final state. Suppose there are 2 states A and B. At A for every alphabet we have 2 option either go to at A or B. Similarly for alphabet at state B we have 2 option either go to at A or B.
Therefore 2 * 2 * 2 * 2 = 16.

---

answer is given 16+4 = 20

---

Apart from the above mentioned 16 DFAs having no final states, we'll have 4 more DFAs having final states. But for final state, we'll have only one choice i.e. except the start state ( if we make start state as final state, it will accept at least one string which is $\varepsilon$ ) So for the final state, we'll have 2 transitions on each input symbol which give us 2*2 = 4 more DFAs :)

Excuse my drawing :P

So in all we have 16 + 4 = 20 DFAs accepting empty language

---

Here as nothing is mentioned about initial state , so choice of initial state also matters..

So total no of DFAs should be :  16 * 2 + 4 * 2  = 32 + 8  = 40

---

@Habibkhan here the states are not mentioned to be distinct.. so how can you distinguish between states? I have named them as per my convenience

---

if the initial state is designated then there will be 20 DFA's otherwise answer will be 40 as explained above.

---

Here are few explainations:

https://gateoverflow.in/15855/calculate-number-dfas-possible-with-designated-initial-state

https://gateoverflow.in/10853/how-many-dfas-exist-with-three-states-over-the-input-alphabet

https://gateoverflow.in/27730/number-of-dfa

https://gateoverflow.in/16808/many-state-drawn-over-alphabet-which-accepts-empty-language

https://gateoverflow.in/61876/minimum-number-of-states-in-dfa

https://gateoverflow.in/11767/the-possible-no-of-dfa-with-three-states

Answer 1

 

 

case1:when no final state to be chosen.

    then dfa possible=2^4=16.

case2:when X is initial state and Y is final state but unreachable from X

  then dfa possible =2^2=4

therefore in total dfa possible is =16+4=20.Ans

Comments

@Vikas202 There may be possible no final state selected