Question

Consider the following types of languages: L₁: Regular, L₂: Context-free, L₃ : Recursive, L₄ : Recursively enumerable. Which of the following is/are TRUE?

I. L̅₃ ∪ L₄ is recursively enumerable

II. L̅₂ ∪ L₃ is recursive

III. L₁^* ∩ L₂ is context-free 

IV. L₁ ∪ L̅₂ is context-free
1. I only
2. I and III only
3. I and IV only
4. I, II and III only

Answer 1

Correct Answer - Option 4 : I, II and III only

L₁: Regular

L₂: Context-free

L₃: Recursive

L₄: Recursively enumerable

Statement I: TRUE

 L̅₃ ∪ L₄ is recursively enumerable

As L₃ is recursive language and complement of a recursive language is also recursive.

L₄ is recursive enumerable. So, L̅₃ ∪ L₄ is recursive enumerable.

Statement II: TRUE

II. L̅₂ ∪ L₃ is recursive

L₂ is context free language. Context free languages are not closed under complementation. Complement of a context free language is context sensitive also recursive. L₃ is recursive.

So, union of two recursive languages is recursive.

Statement III: TRUE

III. L₁^* ∩ L₂ is context-free 

Kleen closure of regular language is regular. Intersection of a regular language and context free language is context free.

Example:

Regular language = \(L^*_1 = (a + b)^*\)

L₂ = aⁿ bⁿ

The intersection of \(L^*_1 \cap L_2 = a^nb^n\) is a context-free language 

Statement IV: FALSE

L₁ ∪ L̅₂ is context-free

Complement of L₂ is not context free.  L₁ ∪ L̅₂ may or may not be context free.

Therefore, the statement I, II and III are correct.