title: "Context-Free Language"

Context-Free Language

Definition. A language is context-free if it is $L(G)$ for some context-free grammar $G$, equivalently if some pushdown automaton recognizes it.

Every regular language is context-free and the containment is proper: $\{0^n1^n\}$ is context-free but not regular. The containment is proper in the other direction too, since $\{a^nb^nc^n\}$ is not context-free, proved by the pumping lemma for context-free languages in Lecture 5. The class is closed under union, concatenation, and star, and under intersection with a regular language, but not under intersection or complement, which is the sharpest difference from the regular languages.