edited by
8,828 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}\}$
edited by

6 Answers

Best answer
15 votes
15 votes

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.

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

35 votes
35 votes
4 answers
2
Kathleen asked Sep 14, 2014
11,381 views
Comparing the time T1 taken for a single instruction on a pipelined CPU with time T2 taken on a non-pipelined but identical CPU, we can say thatT1 ≤ T2T1 ≥ T2T1 < T2T...
40 votes
40 votes
4 answers
3
Kathleen asked Sep 14, 2014
10,291 views
Let $L$ denote the languages generated by the grammar $S \to 0S0 \mid 00$.Which of the following is TRUE?$L = 0^+$$L$ is regular but not $0^+$$L$ is context free but not ...
28 votes
28 votes
5 answers
4
Kathleen asked Sep 14, 2014
11,369 views
Let $S$ and $T$ be languages over $\Sigma=\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$, respectively. Which of the following is true?$S \subs...