Finite Automata

Question

How many different finite automata are possible with three states x, y and z over the alphabet {a, b} where x is always the start state.

Justify your Answer with Example .

Answer 1

N*N^(N*M)*2^N

The LHS N = 1...as only one way to select initial state i.e x

N^(N*M) is no of transition functions i.e 3^6

2^N is possibilities of final states i.e 2^3

finally there are = 1*3^6*2^3 =5832 dfa's

Comments

if you are asking about FA...it can be both NFA or DFA....number of dfa's is already known 5832..now for nfa's only change will be in transition fn .....here number of transition functions will be 8^6...rest will be same

---

Ans is right...

---

how  no of  transition in case of nfa are 8^(6)

Answer 2

(4*4*4)+(4*4*4)=128

Taking 'Z' as final state, x has 4 option to move  with (a,b) over (x,y) (2*2)and similarly y and z have four option.Similarly when "Y" has final state.

Comments

how did you reach the answer .You said what if either z is final state or y is a final state .But how about if x is a final state .I said x  should be a start state but did not say it can't be a final state . at the same time it can be both final as well as start state in that case answer will differ .........please explain a little bit more so i can understand how did you get this answer.

---

What is correct answer

---

I don't know . If i knew it why would i ask you ?