Consider the following languages.
L0 = {0^p 1^q 0^r | p, q, r >= 0}
L1 = {0^p 1^q 0^r | p, q, r >= 0, p = q}
L2 = {0^p 1^q 0^r | p, q, r >= 0, 0_p != r}
Which one of the following statements is FALSE?
A. L0 is context-free.
B. L1 is context-free.
C. Complement of L2 is recursive.
D. Complement of L0 is context-free but not regular.
GATE 2013 · Theory of Computation · Identify Class Language · medium
Answer: Statement D ('Complement of L0 is context-free but not regular') is FALSE because L0 is regular and complement of a regular language is regular. Answer: D
Analyze L0: L0 = {0^p 1^q 0^r | p,q,r >= 0} = the set of all strings matching the regex 0*1*0*. A DFA for this language: State 0 (reading leading 0s) -> State 1 (reading 1s) -> State 2 (reading trailing 0s), with appropriate transitions. All states are accepting. L0 is REGULAR.
Check statement A: L0 is regular. Every regular language is also context-free. So 'L0 is context-free' is TRUE.
Check statement B: L1 requires p=q (equal leading 0s and 1s). PDA: push each leading 0, then pop for each 1. If stack is empty after reading 1s, accept any trailing 0s. L1 is CFL. Statement B is TRUE.
Check statement C: L2 = {0^p 1^q 0^r | p != r}. Complement of L2 in 0*1*0* = {0^p 1^q 0^p | q >= 0} which is CFL. The full complement(L2) = Sigma* \ L2 includes strings not in 0*1*0* (which form a regular set) plus {0^p 1^q 0^p}. CFL union Regular = CFL. So complement(L2) is CFL and hence recursive. Statement C is TRUE.
Check statement D: Statement D says 'Complement of L0 is context-free but not regular.' But L0 = 0*1*0* is REGULAR. Complement of a regular language is regular (DFAs are closed under complement by flipping accept/reject states). Therefore complement(L0) is REGULAR — not merely 'CFL but not regular.' Statement D is FALSE.