GATE CSE 2017 Set 1 | Question: 38

Question

Consider the following languages over the alphabet $\Sigma = \left \{ a, b, c \right \}$. Let $L_{1} = \left \{ a^{n}b^{n}c^{m}\mid m,n \geq 0 \right \}$ and $L_{2} = \left \{ a^{m}b^{n}c^{n}\mid m,n \geq 0 \right \}$.

Which of the following are context-free languages?

1. $L_{1} \cup L_{2}$
2. $L_{1} \cap L_{2}$

• A. I only
• B. II only
• C. I and II
• D. Neither I nor II

Comments

1 is TRUE because L1 union L2 is { a^p b^q c^r | p=q or q=r }. It took me so long to find out😒. 

2. is False as L1 intersection L2 is { a^n b^n c^n | n>=0}.

---

Both the languages are CFL and CFL is closed under union and not closed under intersection so A.

---

@tusharb You can use closure property to say “yes” – so first part is correct. But using it to say “no” is wrong as it depends on the given instance. Intersection of 2 CFLs can give another CFL.

---

Arjun sir yes I totally didn’t think about that case, thanks for the heads up

Answer 1

Union and Intersection NPDA

 

L1 and L2 with NPDA and l1 union l2

Answer 2

The L1 is deterministic CFL  with final state accepted by both empty stack and final state. 

L2 is deterministic CFL with final state accepted by final state only. 

Union of two CFL is a CFL but intersection of two CFL can/cannot be CFL. Hence option A is correct