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

3 Answers

1 vote
1 vote
128 DFA possible
by
0 votes
0 votes

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.

2 Comments

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

so 2^4*2^2 = 2^6 = 64 possible states.
0
0
why initial state is fixed ?? no. of ways to select initial state = 2 ... so I think ans should be 2*64 = 128
0
0
0 votes
0 votes

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
0
0