Search code examples
intersectionregular-languagecontext-free-language

Determine if a language is context free


Lets say you have a language L and you want to determine if it is context free. Context free languages intersected with regular languages are context free. Is that enough to prove that L is context free?

Meaning,

L intersect P = T Where P is a regular language and T is context free. Does this imply that L is context free?


Solution

  • No, your statement is not true. Consider the following counter-example:

    L = {0n1n2n | n > 0}, P = T = Ø. Clearly we have L ∩ P = L ∩ Ø = Ø = T, and Ø is both regular and context-free.

    Note it is well-known that L is not context-free (see example on p.12 for a sketch proof by pumping lemma).