UGC NET CSE | December 2015 | Part 3 | Question: 27

Question

There are exactly ____ different finite automata with three states $x$, $y$ and $z$ over the alphabet $\{a,b\}$ where $x$ is always the start state

• A. $64$
• B. $256$
• C. $1024$
• D. $5832$

Comments

https://gateoverflow.in/40678/finite-automata

---

2^(2^3) =256 ?? not sure though

Answer 1

let no of states are n and no of symbols are m.

nc0 + nc1 + nc2 + ....+ncn =2ⁿ

3c0(no final state) + 3c1(one final state) + 3c2(two final states) + 3c3(3 final final states) = 2^3

at every state for one input symbol there is possible 3 transition.

Transition Function	Input( a)	Input( b)
State X	3	3
State Y	3	3
State Z	3	3

so ans should be=2^3 * 3^6 (Fixed Initial state)

if no initial state fixed then ans should be=3 * 2^3 * 3^6

For NFA at each state having 8 possible transition (none,x,y,z,xy,yz,xz,xyz) for single input symbol

Transition Function	input(a)	input(b)
State X	8	8
State Y	8	8
State Z	8	8

So ans should be= 2^3 * 8^6 (Initial state is fixed)

                            =3 * 2^3 * 8^6 (if no initial state is fixed)

Let Total no.of states = n, Total no.of symbols =m

total no of dfs = (2ⁿ ) *( n^nm)

total no.of nfa's =  (2ⁿ ) * (2ⁿ)^{^(nm)}

above result is assuming initial state is fixed.

if initial state is not fixed than multiply by no of states.

Comments

what about e - NFA , how many ?

---

i think adding one more symbol..(m+1) like this...

Answer 2

at input 'a' of  x, transition can be to any of the 3 states x or y or z= 3 choices

at input 'b' of  x , transition can be to any of the 3 states x or y or z= 3 choices

similarly for y= 3 choices for 'a' and 3 choices for 'b'

and for z= 3 choices for 'a' and 3 choices for 'b'

 

total state transition choices=3^6

x can be accepting or non- accepting state=2choice

y can be accepting or non- accepting state=2choice

z can be accepting or non- accepting state=2choice

total type of state choices=2^3

total Automata=2^3*3^6

Answer 3

No. of possible DFA = No, of start state x No of possible final states x

(No of possible functions from a set containing (No. of states x No, of input symbols= 6) elements to a set containing (No. of input symbols = 2) elements ) [ = 2^6 = 64]

The final product term above takes into account the total number of transitions possible.

So, required answer = 1 x 3 x 64= 192

Comments

(No of possible functions from a set containing (No. of states x No, of input symbols=6) elements to a set containing (No. of states= 3) elements ) [ = 3^6 ]