edited by
8,829 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

1 votes
1 votes

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

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

35 votes
35 votes
4 answers
2
Kathleen asked Sep 14, 2014
11,383 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...