Consider the following languages over the alphabet \(\Sigma = \left \{ a, b, c…
2017
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?
I. \(L_{1} \cup L_{2}\)
II. \(L_{1} \cap L_{2}\)
- A.
I only
- B.
II only
- C.
I and II
- D.
Neither I nor II
Attempted by 30 students.
Show answer & explanation
Correct answer: A
Answer: only the union L1 ∪ L2 is context-free.
L1 is context-free. Example grammar: S -> a S b | T ; T -> c T | ε, which enforces equal numbers of a and b and allows any number of c.
L2 is context-free. Example grammar: S -> a S | U ; U -> b U c | ε, which allows any number of a and enforces equal numbers of b and c.
Since context-free languages are closed under union, L1 ∪ L2 is context-free.
For the intersection, any string in both languages must satisfy: number of a's = number of b's (from L1) and number of b's = number of c's (from L2). Thus L1 ∩ L2 = { a^n b^n c^n | n ≥ 0 }.
The language { a^n b^n c^n | n ≥ 0 } is a standard non–context-free language, so L1 ∩ L2 is not context-free.
Conclusion: L1 ∪ L2 is context-free, but L1 ∩ L2 is not, so the correct choice is that only the union is context-free.
A video solution is available for this question — log in and enroll to watch it.