Question

Consider the following languages over the alphabet ∑ = {a, b, c}

Let L₁ = {aⁿ bⁿ c^m | m, n ≥ 0} and L₂ = {a^m bⁿ cⁿ | m, n ≥ 0}

Which of the following are context-free languages?

I. L₁ ∪ L₂

II. L₁ ∩ L₂

1. I only
2. II only
3. I and II
4. Neither I nor II

Answer 1

Correct Answer - Option 1 : I only

CFL Properties:

1) Union of two context free languages is context free.

2) Intersection of two context free languages may or may not be context free.

L₁ = {aⁿ bⁿ c^m | m, n ≥ 0}

This language is DCFL and hence CFL.  As number of a’s are equal to number of b’s in this. Hence, only one stack is needed.

L₂ = { a^m bⁿ cⁿ | m, n ≥ 0}

This language is also DCFL and hence CFL also. In this, number of b’s are equal to number of c’s, so, one stack is needed for this.

Now, from properties of CFL it is clear that union of two CFL is CFL.

So, statement 1 is correct

Statement 2 is correct.

 intersection of two CFL may or may not be CFL.

For, L₁ ∩ L_2, we require two stacks, which becomes the case of context sensitive language. L₁ ∩ L₂ is not a CFL. So, option 2) is incorrect.