2.4 CFL Properties

If $L_1$ and $L_2$ are context-free languages, then so are:

• $L_1 \cup L_2$
• $L_1 L_2$
• $(L_1)^*$

You could genertate new Grammars to prove them easily.

But the intersection of two CFL are not necessary Context-free.

Because a stack cannot record the actions of pop and push from two CF languages at the same time.

Example:

, which is not CF

If $L$ is CF, $R$ is regular. Then $L \cap R$ is CF, $L \backslash R$ is CF.

Why?

If L is Context-free, then $L^{rev}$ is also context free.

You could just convert L into CNF, then switch the sequence.