Consider the following languages. \(L_1 = \{a^p \mid p \text{ is a prime…
2017
Consider the following languages.
\(L_1 = \{a^p \mid p \text{ is a prime number} \}\)
\(L_2 = \{ a^nb^mc^{2m} \mid n \geq 0, m \geq 0 \}\)
\(L_3 = \{a^n b^n c^{2n} \mid n \geq 0 \}\)
\(L_4 = \{ a^n b^n \mid n \geq 1\}\)
Which of the following are CORRECT?
I. \(L_1\) is context free but not regular
II. \(L_2\) is not context free
III. \(L_3\) is not context free but recursive
IV. \(L_4\) is deterministic context free
- A.
I, II and IV only
- B.
II and III only
- C.
I and IV only
- D.
III and IV only
Attempted by 99 students.
Show answer & explanation
Correct answer: D
Conclusion: only the statement about L4 is correct. None of the provided answer choices lists L4 alone, so no choice is fully correct.
L1 = {a^p | p is prime}: Not regular and not context-free. Unary context-free languages are ultimately periodic (membership stabilizes to a union of arithmetic progressions), but the set of prime lengths is not ultimately periodic, so L1 cannot be context-free. (L1 is decidable/recursive, but not context-free.)
L2 = { a^n b^m c^{2m} | n ≥ 0, m ≥ 0 }: Context-free (in fact regular). It equals a* (b c^2)*. Example grammar: S -> A B, A -> aA | ε, B -> b B cc | ε.
L3 = { a^n b^n c^{2n} | n ≥ 0 }: Context-free. A simple grammar is S -> a S b cc | ε, which generates a^n b^n c^{2n}. Therefore the claim that L3 is not context-free is false.
L4 = { a^n b^n | n ≥ 1 }: Deterministic context-free (classic example accepted by a deterministic pushdown automaton).
Final remark: Only the statement about L4 is true. Since none of the answer choices corresponds to "IV only," none of the provided choices is correct.
A video solution is available for this question — log in and enroll to watch it.