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?

The correct answer is “option 4”.

EXPLANATION:

Option 1:  TRUE

Language L₁ can be written as 0*1*0*.

So, L₁ is a regular language.

Language L₂ has one comparison p! = r.

So, L₂ is a Context-free language.

Option 2:  TRUE

According to the closure property of context-free language, intersection of a regular language with Context-free language is also Context-free language.

 So, L1 ∩ L2 is context-free.

Option 3:  TRUE

According to the closure property of context-free language (CFL), it is not closed under complementation.

So, L₂ can be assumed as Context-sensitive language (CSL) since every CFL is CSL.

Also, CSL is closed under complementation and every CSL is recursive.

So complement of L₂ is CSL & hence recursive.

Option 4:  FALSE

According to the closure property of regular language, it is closed under complementation.

So, complement is L₁ also regular.

Hence, the complement of L1 is context-free but not regular is false.

The correct answer is “option 4”.