Question

Consider the following languages.

L1 = {aᵖ | p is a prime number}
L2 = {aⁿbᵐc²ᵐ | n ≥ 0, m ≥ 0}
L3 = {aⁿbⁿc²ⁿ | n ≥ 0}
L4 = {aⁿbⁿ | n ≥ 1}

Which of the following are CORRECT?

I. L1 is context-free but not regular.
II. L2 is not context-free.
III. L3 is not context-free but recursive.
IV. L4 is deterministic context-free.

Accepted Answer

The correct answer is (D) III and IV only. L1 is a unary language (single-letter alphabet); a classical theorem states every unary context-free language is regular. Since {a^p | p prime} is not regular (the primes aren't eventually periodic), it also can't be context-free — so I is false. L2 = aⁿ·(bᵐc²ᵐ) IS context-free (a simple CFG matches each b to two c's while n is unconstrained), so II ('L2 is NOT context-free') is false. L3 requires matching THREE quantities simultaneously (n, n, 2n), which is beyond any single-stack PDA — not context-free — but it is still recursive (easily decided by counting), so III is true. L4 = aⁿbⁿ is the textbook example of a deterministic context-free language (accepted by a DPDA that pushes on a's and pops on b's), so IV is true. Correct: III and IV.

Explanation