Theory of Computation · topic
Closure of CFLs and DCFLs, including intersection with a regular language, decidable and undecidable questions for CFGs, the pumping lemma for CFLs with block arguments, closure proofs of non-context-freeness and the standard non-CFL languages.
Context-free languages are closed under union, concatenation, star, reverse and homomorphism, and under intersection with regular languages. They are not closed under intersection or complement. Membership, emptiness and finiteness are decidable for CFGs; equivalence and regularity are not.
The pumping lemma for context-free languages gives a necessary condition on every CFL. It is used to prove that languages such as a^n b^n c^n and ww are not context-free. The decomposition has five pieces uvxyz with constraints that reflect a repeated path in a CNF parse tree.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
