GATE CSE 2000 | Question: 2.8

Question

What can be said about a regular language $L$ over $\{ a \}$ whose minimal finite state automaton has two states?

• A. $L$ must be $\{a^n \mid n \  \text{ is odd}\}$
• B. $L$ must be $\{a^n \mid n \  \text{ is even}\}$
• C. $L$ must be $\{a^n \mid n \geq 0\}$
• D. Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$

Comments

it's wrong question. The statement will be 

" Either L can be  {aⁿ | n is odd} or L can be {aⁿ | n is even}"

---

"must be" needs to be replaced with "can be" because the language with two states in minimal dfa can be some something else too like a^+.

---

or is inclusive or  so either must be even  or odd or both

---

0 is not even nor odd right. Then d is surely correct.

Answer 1

option A require two states in MFA
option B require two states in MFA
option C require one states in MFA
option D is union of option A and B so if we find DFA for union we get two states then it further minimized to only one state ( both state will be final state in union) 

Answer is A,B
correct me if wrong :)

Comments

> You are going to pick only one option. So D is the ans.
> The keyword "must" clearly makes option A & B false.

---

What if n = 0 then {aⁿ | n is even} boils down to {a⁰} = {Epsilon}. But Two state is not required to accept Epsilon. Where am I wrong ?

---

Why I and II are not same, @Ahwan sir?

Answer 2

Answer: (D)

Explanation: There are two states. When first state is final, it accepts even no. of a’s.

                       When second state is final, it accepts odd no. of a’s.