-
Consider the following languages :
L1 = { 0p 1q 0r | p, q, r ≥ 0 | }
L2 = { 0p 1q 0r | p, q, r ≥ 0 , p ≠ r | }
Which one of the following statements is false?
-
- L2 is context-free
- L1 ∩ L2 is context-free
- Complement of L2 is recursive
- Complement of L1 is context-free but not regular
Correct Option: D
L1 = { 0p 1q 0r | p, q, r ≥ 0 }
L2 = { 0p 1q 0r | p, q, r ≥ 0 , p ≠ r }
(a) L2 is context Free - true
We can accept, or reject L2 with single stack. Insert P 0's into stack skip q 1's.
For each 0 corresponding to r, remove 0 from stack.
(b) L1 ∪ L2 is context Free - true
Here L1 ∩ L2 = L2 which is context Free.
(c) Complement of L2 is recursive - true
L2 is Context-Free language
Complement of CFL may or may not be CFL.
Complement by CFL is definately recursive.
(d) Complement of L1 is Context Free, but not regular false.
L1 = { 0p qq 0r | p, q, r ≥ 0 } 
Which is regular,
Hence, the answer is (d).
