Skip to content

2.4 CFL Properties

If and are context-free languages, then so are:

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 is CF, is regular. Then is CF, is CF.

Why?

If L is Context-free, then is also context free.

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