Project ForgeConsider the following languages.
L1 = {0^p 1^q 0^r | p,q,r ≥ 0}
L2 = {0^p 1^q 0^r | p,q,r ≥ 0, p ≠ r}Which one of the following statements is FALSE?
- AL2 is context-free.
- BL1 ∩ L2 is context-free.
- CComplement of L2 is recursive.
- Complement of L1 is context-free but not regular.
Explanation
L1 = 0*1*0* is actually REGULAR (no constraint links p and r). L2 = {0^p1^q0^r | p≠r} is a classic context-free-but-not-regular language (A is TRUE). Since L2 ⊆ L1, L1∩L2 = L2, which is context-free (B is TRUE). Every context-free language is decidable (recursive), and recursive languages are closed under complement, so complement of L2 is recursive (C is TRUE). But since L1 itself is REGULAR, its complement is also regular (regular languages are closed under complement) — so 'context-free but not regular' is FALSE for complement of L1, making D the false statement.
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.