What can be said about a regular language L over {a} whose minimal finite…
2000
What can be said about a regular language L over {a} whose minimal finite state automaton has exactly two states forming a 2-cycle on the input a?
- A.
L must be {an| n is odd}
- B.
L must be {an| n is even}
- C.
L must be {aⁿ | n ≥ 0}
- D.
Either L must be {an | n is odd}, or L must be {an | n is even}
Attempted by 33 students.
Show answer & explanation
Correct answer: D
With two states forming a cycle on input a, the automaton alternates between the two states after each symbol. Thus the two states represent the parity of the length of the input string.
If the start state is final, the language is {aⁿ | n is even}. If the other state is final, the language is {aⁿ | n is odd}. If both states or neither state were final, the language would be all strings or the empty language, each of which has a smaller one-state minimal DFA. Therefore, for a two-state minimal parity automaton, L must be either the even-length language or the odd-length language.