Consider the following languages. L 1 = {0 p 1 q 0 r | p, q, r ≥ 0} L 2 = {0 p 1 q 0 r | p, q, r ≥ 0, p ≠ r} Which one of the following statements is FALSE?

Correct Answer is : Complement of L1 is context-free but not regular

Complement of L 2 is recursive.

Complement of L 1 is context-free but not regular

GATE Computer Science (CS) 2013 Solved Paper

Question : 42 of 65

Marks: +1, -0

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?

L₂ is context-free.
L₁ ∩ L₂ is context-free.
Complement of L₂ is recursive.
Complement of L₁ is context-free but not regular

Validate

Go to Question:

Prev Question

Next Question