Virtual Gate Test Series: Theory Of Computation - Finite Automata

Question

How many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything?

answer is 20 or 64?

Comments

20

---

pls share the solution. I'm getting 64

---

Share your solution, i will check !

Note that they are asking the FA for (a+b)*

---

first we've to map 4 combinations of states and I/P symbol to two states [QxΣ->Q]

[(X, a), (X, b), (Y,a), (Y, b)] --> [X, Y]

so we get $2^4$=16

initial state is X=1 choice

final states we've 2*2 choices

so total 16*2*2*1=64

 

pls tell where I'm going wrong

Answer 1

20 is right.

 

 

 

 

Comments

@srestha 

In the qxn it is no where mentioned as minimal DFA's.

---

@srestha in minimal DFA when several states are combined then it forms one state not multiple state. Eg- if q1 and q2 are combined to form {q1, q2} then it is a single state. hence, there can be only one transition only for a given input

also

nothing about the DFA has been mentioned in the question. so we assume that it is in minimal form

---

ok understood

thanks :)