DFA

Question

How many number of DFA's are possible with 2 states X and Y for input alphabet {0,1}?

Answer 1

128 DFA possible

Answer 2

Initial state is fixed. Now from initial state, transitions for symbols aa and bb can be to any of the 2 states, so there are 2*2=2² possibilities. Similarly, for 2nd state, there are 2² possible transitions for each state i.e. we have 2² * 2²=2⁴ possible transitions.

i.e.,2^4=16 possible states.

Comments

I think this should be as N * N^(N*M) * N^2

so 2^4*2^2 = 2^6 = 64 possible states.

---

why initial state is fixed ?? no. of ways to select initial state = 2 ... so I think ans should be 2*64 = 128

Answer 3

https://gateoverflow.in/63719/no-of-dfa

According to the formula derived above, the answer should be 128

The formula goes like n^(n*m) * 2^n

Here n = 2 and m =2.

But initial state in this case is not fixed, so we multiply by 2 again.

So ans is 128

Comments

n*n^(n*m)*2^(n) = 128 if initial state is not fixed here