Consider the following languages: Minimum number of states in DFA for the…
Consider the following languages:
Minimum number of states in DFA for the above languages:
I. for L1: four states
II. for L2: only one state
III. for L3: only two states
IV. for L4: only four states
Which of the following statements is true?
Answer: C. L2 and L3 only — Answer: The true statements are the second and the third (L2 and L3 only). L1: L1 = { a^{m^n} | n ≥ 1, m ≥ n } is not regular. It requires comparing unbounded…
- A.
I and IV only
- B.
L2, L3, and L4 only
- C.
L2 and L3 only
- D.
Only I
Attempted by 51 students.
Show answer & explanation
Correct answer: C
Answer: The true statements are the second and the third (L2 and L3 only).
L1: L1 = { a^{m^n} | n ≥ 1, m ≥ n } is not regular. It requires comparing unbounded exponent relationships (similar in difficulty to languages that force unbounded numeric relationships), so there is no finite-state DFA that recognizes it. Hence the claim that it needs four states is false.
L2: L2 = { ω(ω^R)* | ω ∈ (a,b)* } equals the set of all strings over the alphabet. For any string s, choose ω = s and use zero repetitions of ω^R, so s ∈ L2. Therefore L2 = (a,b)* and its minimal DFA has one state (the start state, which is accepting).
L3: L3 = { ω ∈ (a,b)* | 3·n_a(ω) + 2·n_b(ω) is even } reduces modulo 2 to n_a(ω) ≡ 0 (mod 2) because 3 ≡ 1 (mod 2) and 2 ≡ 0 (mod 2). So L3 is exactly the set of strings with an even number of a's. The minimal DFA for parity of a's requires two states.
L4: L4 = { w x y x | w, x, y ∈ (a,b)^+ } requires matching two identical arbitrary-length substrings x separated by y. This equality of unbounded substrings is analogous to the non-regular language {ww}, so L4 is not regular and cannot be recognized by any finite-state DFA (in particular not by a four-state DFA).
Conclusion: Only the second and third statements are true; hence the correct selection is the one that states that L2 and L3 only are true.