1.8k views

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

1. $L$ must be $\{a^n \mid n \ \text{ is odd}\}$
2. $L$ must be $\{a^n \mid n \ \text{ is even}\}$
3. $L$ must be $\{a^n \mid n \geq 0\}$
4. Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$
edited | 1.8k views
+4

it's wrong question. The statement will be

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

0
"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^+.
0
@suvasish If you think what if there is no final state so it should be "may be", then you are wrong in that case minimal DFA will have one state only, not two.

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.

edited
0

Is it not a wrong question?

Explanation- Option D) states that- L "must be"  {a| n is odd}, or L must be {a| n is even}

But, L can also be-

L={a| n>0 }

or

L={epsilon}

Both the Languages also need two states in the minimum DFA.

Ans 4) Either L must be  {a| n is odd}, or L must be {a| 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.

+1 vote

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)

correct me if wrong :)

+1

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.

0
ok that i got now , but option A and B also have only 2 states in MFA
+1
> You are going to pick only one option. So D is the ans.
> The keyword "must" clearly makes option A & B false.
0

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

a. DFA needs two states, make second state final.
b. DFA needs two states, make first state final.
c. DFA needs one state, make that state final.
d. DFA needs two states, make both the states final.

edited
i am getting option a and b.
–1 vote

Ans: D Either L must be  {a| n is odd}, or L must be {a| n is even}

1
2