it's wrong question. The statement will be

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

5,153 views

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

- $L$ must be $\{a^n \mid n \ \text{ is odd}\}$
- $L$ must be $\{a^n \mid n \ \text{ is even}\}$
- $L$ must be $\{a^n \mid n \geq 0\}$
- Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$

Best answer

The question is not precise here. Since, minimal DFA has two states exactly one must be final. Because if

- No state is final, no strings can be accepted and for this only one state is required in the minimal DFA
- If both the states are final, then they can be merged to a single state and hence it won’t be a minimal DFA

Now, with one final state and two states

- if we make a transition on first $a$ to final state and stay there for any remaining number of $a’s$, the language we get is $L=\{a^n \mid n > 0\}$ which is $a^* – \{\epsilon\}$
- Like in above we do the transition must if the initial state is made final, then the only string accepted is $\epsilon$

The above two cases are ignored in the given options.

The remaining possibility is for each input symbol $a,$ the DFA transitions between the first and second states. Then,

- if initial state is final we get $L = \{a^n \mid n \text{ is even} \}$
- if initial state is not final we get $L = \{a^n \mid n \text{ is odd} \}$

So, none of the options is correct though D is the best option to pick.

Answer is (**D**). Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$

Because if we draw the minimal dfa for each of them, we will get two states each.

Whereas, $\{a^n \mid n \geq 0\}$ requires only one state.

**@indra kumar sahu** Then it can be reduced to single state,

I further agree with **@rohith1001 **and indeed option **D** is not accurate

Ans 4) Either L must be {a^{n }| n is odd}, or L must be {a^{n }| n is even}

option A) Wrong because even case can also be true.

option B) Wrong because odd case can also be true.

option C) A regular language L over {a} with 2 states can have both final states and hence this can also be true. BUT in the question it is mentioned **"whose minimal finite state automaton has two states". So if we want to accept all strings the minimal finite state automaton, it will contain 1 state (minimum). Since in the question it is mentioned 2 states in minimal finite automata hence (D) is the correct option.**

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 :)

edited
Sep 4, 2017
by Ahwan

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 }| n is odd}, or L must be {a^{n }| n is even}

II) L must be {a^{n }| n is odd || n is even}

I and II are not same.

Search GATE Overflow