Let L1 , L2 be any two context-free languages and R be any

Home » Theory of Computation » Theory of computation miscellaneous » Question

Let L₁ , L₂ be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT ?
I. L₁ ∪ L₂ is context-free.
II. L₁ is context-free.
III. L₁ – R is context-free.
IV. L₁ ∩ L₂ is context-free.

1. I , II and IV only
2. I and III only
3. II and IV only
4. I only

Correct Option: B

1. L₁ ∪ L₂ is context-free because the union of two context free language is always a context free or CFL are closed under union operation. So, it is correct.
2. L₁ is not context-free because CFL are not closed under complement operation. So, it is incorrect.
3. L₁ - R is context-free because if context-free language is intersection to the complement of regular language then it is always context-free. L₁ - R = L₁ ∩ R₁, so it is correct.
4. L₁ ∩ L₂ is not context-free because context-free languages are not closed under complement operations. So it is incorrect.