Question

Consider the following languages

L₁ = {0^P 1^q 0^r | p, q, r ≥ 0}

L₂ = {0^P 1^q 0^r | p, q, r ≥ 0, p ≠ r}

Which one of the following statements is FALSE?

(A) L₂ is context-free

(B) L₁ ∩ L₂ is context-free

(C) Complement of L₂ is recursive

(D) Complement of L₁ is context-free but not regular

Answer 1

(D) Complement of L₁ is context-free but not regular

(A) L₂ is CFL (True)

(B) L_1 ∩ L₂ = CFL (True)

(C) L₂ complement is recursive (True)

(D) L complement is CFL but not regular (False) as L₁ is regular L₁ is regular