Back to the 2025 paper

Module 2: Context-Free Languages (CFL) and PDA

20252m

Context-free languages are NOT closed under

(i) Union
(ii) Concatenation
(iii) Intersection
(iv) Kleene star

Worked SolutionAI Assisted

Answer

Correct Option: (iii) Intersection

Explanation

Closure properties of Context-Free Languages (CFLs):

Operation Closed?
Union L1∪L2L_1 \cup L_2 Yes – S→S1∣S2S \rightarrow S_1 \mid S_2
Concatenation L1L2L_1L_2 Yes – S→S1S2S \rightarrow S_1S_2
Kleene star L∗L^* Yes – S→SS1∣ϵS \rightarrow SS_1 \mid \epsilon
Intersection L1∩L2L_1 \cap L_2 No
Complement L‾\overline{L} No

Counterexample for intersection:
L1={anbncm∣n,m≥0}L_1 = \{a^n b^n c^m \mid n,m\ge0\} (CFL), L2={ambncn∣n,m≥0}L_2 = \{a^m b^n c^n \mid n,m\ge0\} (CFL)
L1∩L2={anbncn}L_1 \cap L_2 = \{a^n b^n c^n\} which is not CFL (pumping lemma).

Since De Morgan: L1∩L2= L1‾∪L2‾ ‾L_1 \cap L_2 = \overline{\,\overline{L_1}\cup\overline{L_2}\,}, non-closure under intersection implies non-closure under complement.

Final Answer

CFLs are NOT closed under Intersection → Option (iii).

Similar questions

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.