Ace Test Series: Theory Of Computation - Finite Automata

Question

How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language?

1. $4$
2. $16$
3. $20$
4. $24$

Answer 1

Answer is 20.

Please find the attachement for Explanation.

Comments

Thanks.. :)

---

@ayushsomani how are the transition for the last four dfas defined...as the first state has all transitions to itself...so how is the state Y reachable?

Answer 2

this is the solution of above question.

if any doubt then ask.

Comments

Thanks.. :)

Answer 3

Hi ,

Pl find snapshot.