HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Why are CFLs not closed under intersection?

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#91321, answer score: 24

Revisions (0)

No revisions yet.