in Theory of Computation edited by
8,814 views
39 votes
39 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
8.8k views

4 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}"

9
9
"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^+.
5
5
or is inclusive or  so either must be even  or odd or both
1
1
0 is not even nor odd right. Then d is surely correct.
0
0

6 Answers

15 votes
15 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

1 comment

If we make first state final then n=0 is also accepted and that is not a even number or a odd number. I guess only n = odd when second is made final state is the correct answer but whatever. I hate gate and their twisted questions.
0
0
39 votes
39 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

4 Comments

IF we declare as a final state to both the state

then ans is?
0
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
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
0
3 votes
3 votes

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

Answer:

Related questions