755 views

3 Answers

1 votes
1 votes
128 DFA possible
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.

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

Related questions

0 votes
0 votes
2 answers
2
Manuj_og asked May 2, 2023
210 views
on seeing a dfa how can we predict the number of states in it?
3 votes
3 votes
1 answer
3
abhinowKatore asked Jan 14, 2023
530 views
Please explain what is difference between $\overline{L(N)}$ and $L(\overline{N}$) ?
0 votes
0 votes
1 answer
4
Dknights asked Nov 19, 2022
317 views
can we solve it with a minimum of 4 states?