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

There is no grammatical error.  (They mean it must be L1 but not L2...... OR   it must be L2 but not L1)

But by option D they want to say either option A or B.... so answer is D.  
but why there will be the union of two languages? 

I) Either L must be  {aⁿ | n is odd}, or L must be {aⁿ | n is even}
II) L must be  {aⁿ | n is odd || n is even}

I and II are not same.

---

ok that i got now , but option A and B also have only 2 states in MFA

---

> 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.