patternMajor
Why are CFLs not closed under intersection?
Viewed 0 times
whycflsareclosedunderintersectionnot
Problem
I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that CFLs are not closed under intersection.
Solution
Let us assume $2$ CFLs $L_1$ and $L_2$ and their corresponding grammars be $S_1$ and $S_2$ respectively.
It is very straightforward to see that the union of the two, represented by the new grammar as
$$S \to S_1 \mid S_2$$
is also a CFG, as the rule of being context-free is still not violated. Context-free grammar
But to prove that they are not closed under intersection, I'll provide an example.
Let $L_1$ and $L_2$ respectively be:
$$L_1 = \{ a^nb^nc^m \mid n, m \ge 0 \}$$
$$L_2 = \{ a^mb^nc^n \mid n, m \ge 0 \}.$$
It is not hard to see that $L_1 \cap L_2$ is
$$L = \{ a^nb^nc^n \mid n, m \ge 0 \},$$
which is not CFL (No PDA cannot accept that language).
Hope this explains.
It is very straightforward to see that the union of the two, represented by the new grammar as
$$S \to S_1 \mid S_2$$
is also a CFG, as the rule of being context-free is still not violated. Context-free grammar
But to prove that they are not closed under intersection, I'll provide an example.
Let $L_1$ and $L_2$ respectively be:
$$L_1 = \{ a^nb^nc^m \mid n, m \ge 0 \}$$
$$L_2 = \{ a^mb^nc^n \mid n, m \ge 0 \}.$$
It is not hard to see that $L_1 \cap L_2$ is
$$L = \{ a^nb^nc^n \mid n, m \ge 0 \},$$
which is not CFL (No PDA cannot accept that language).
Hope this explains.
Context
StackExchange Computer Science Q#91321, answer score: 24
Revisions (0)
No revisions yet.