Test by Bikram | Mock GATE | Test 2 | Question: 46

Question

The number of possible Deterministic Finite Automation with two states $q_0$ and $q_1$, where $q_0$ is always the initial state over the alphabet $\left \{ a,b \right \}$ which accept empty language is : ____________.

Answer 1

Given,

Machine = DFA.

Input alphabats = { a,b}

No. of states = 2 { q0, q1}.

Initial state = q0.

Language accepted = phi.

---

case-1. When both q0 and q1 are non-final. 

Total possible transition at q0 = 2 * 2  { 2 for a and 2 for b}

Total possible transition at q1 = 2 * 2  { 2 for a and 2 for b}

Total possible config. for eqv. DFA = 4 * 4 = 16

---

case- 2. When q0 - non-final and q1- final.

Total possible transition at q0 = 1 { a and b can not make a trasition to final state q1 other wise accepted language whould not be phi.}

Total possible transition at q1 = 2 * 2  { 2 for a and 2 for b}

Total possible config. for eqv. DFA = 1* 4 = 4.

---

total No. of possible DFA’s = 16+4 = 20

Comments

they are asking for fa not neccessarily dfa

you are forgetting having a transition on a is diffrent then having a transition on a,b

---

https://gateoverflow.in/16808/many-state-drawn-over-alphabet-which-accepts-empty-language

---

@Arjun sir, how we check that whether a string is accepted or not by a fa ? i think we check it by examining that whether the halting state is final or non final. If the start state is not final or no state is final, then how to say that empty language is accepted by it??