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

128 DFA possible
by

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=22 possibilities. Similarly, for 2nd state, there are 22 possible transitions for each state i.e. we have 22 * 22=24 possible transitions.

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

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

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

### 1 comment

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

1
105 views