Finite Automata

Question

There are exactly ______different finite automata with 3 states x,y,and z over the alphabet {a,b} where x is always the start state

1)64 2) 256 3) 1024 4)5832

Answer 1

=(2^x )*( x)^(xy)

= 2^3 * 3^(2*3)

=5832

Here  x= no.of states and y=no of symbols

Comments

In the question, they are asking for number of finite automata so calculation could be....

= ( 2^x) * ((2^x)^(xy))

= (2^3) * ((2^3)^6)   [x=no of states=3 ;  y=no of input symbols=2]

= 2^3 * 8^6

= 2097152

But no option is given like 2097152 so we have to assume that they are only asking for number of "DFAs" and in that case 5832 is the correct answer.

Answer 2

https://gateoverflow.in/11767/the-possible-no-of-dfa-with-three-states

Answer 3

The way to get the answer for such questions is as follows:

$n*n^{n*m}*2^{n}$

(i) The first $n$ denotes that any of the $n$ states can be the initial state. Each of these possibilities may lead to a different output and must be considered.

(ii) The term : $n^{n*m}$ can be thought of as follows:

Let $A,B,C$ be the three states. and $0$,$1$ be the input alphabets

 

The first set denotes the possibilities of transitions that each of the states have on all input alphabets. Every element of the $1st$ set can be mapped to all elements of the $2nd$ set. This is because, a state, on an input alphabet has the opportunity to go to any of the states.

Each element of the first set has $3$ possibilities(to map to $A$ or $B$ or $C$) and there are $6$ such elements. Thus, totally $3^6 = 729$ combinations are possible.

(iii) The $2^{n}$ denotes that any combination of the $n$ states can form the set of Final states.

$Set of final states =$ {{ },$A,B,C,AB,BC,AC,ABC$}

 

Now, in the given question, start state is fixed. So it can be chosen only in $1$ way.

The $n^{n*m}$ will be $3^{3*2} = 3^6 = 729$

And number of final states will be $2^3 = 8$

$\therefore$ Total number of possible DFAs will be : $1*729*8 = 5832$