in Theory of Computation edited by
5,153 views
32 votes

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}\}$
in Theory of Computation edited by
5.2k views

3 Comments

it's wrong question. The statement will be 

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

8
"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^+.
1
or is inclusive or  so either must be even  or odd or both
0

Subscribe to GO Classes for GATE CSE 2022

6 Answers

3 votes
 
Best answer

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

  1. No state is final, no strings can be accepted and for this only one state is required in the minimal DFA
  2. 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

  1. 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\}$
  2. 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,

  1. if initial state is final we get $L = \{a^n \mid n \text{ is even} \}$
  2. 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.

by
36 votes

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 by

5 Comments

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.

2

@Daaku Red Panda

You are right.

For L={a$^{n}$ | n>0 }. We need 2 states in the minimal FA.

But for L={epsilon}. The minimal FA has only 1 state.

0
IF we declare as a final state to both the state

then ans is?
0

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

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

1

We can also use this finite automaton for accepting

all odd length string, all strings starting with a,all strings starting with b.. etc.

so here the key word “must be” is not appropriate. Right?

0
3 votes

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) 

Answer is A,B
correct me if wrong :)

5 Comments

edited by

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.

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

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 ?

0

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

0
1 vote

Correct answer is (D) only.
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 by
0 votes

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.

Answer:

Related questions