3,351 views

2 Answers

Best answer
6 votes
6 votes

if we have n states and k input symbols and assuming that the no of final state may be any subset of these n states.

no of ways to choose initial state = 1 (as the intial state is fixed)

no of final state = 2^n (as we have two possibility -->1> choose a state and keep in our subset of final state or  2>do not choose it)

no of different dfa assuming no final state and no initial state is n^(n*k) because 

   input alphabate                                 a                            b

state1  dfa can go to any of the 3 staes dfa can go to any of the 3 staes
state 2 dfa can go to any of the 3 staes dfa can go to any of the 3 staes
state3 dfa can go to any of the 3 staes dfa can go to any of the 3 staes

so,total no of state= (no of way to select initial state)(no of way to select final state)(no of way to select different dfa with is not designated by a final state or initial state)

  = 1*2^n*n^(k*n)

0 votes
0 votes

if no of I/p symbols are m

and if no of states are n 

then no of final states are possible is 2n

and no of DFA's  possible are 2n * nn^m

Related questions

4 votes
4 votes
3 answers
1
AnilGoudar asked Apr 1, 2017
3,829 views
How many 3 state DFA's can be constructed with a designated initial final state that accepts empty language over alphabet {a,b}?
33 votes
33 votes
3 answers
2
1 votes
1 votes
3 answers
3
Prajwal Bhat asked Feb 4, 2017
1,130 views
The number of different DFA's with two states X and Y,where X is the initial state,over the alphabet $\sum$ = {0,1,2}