Context-Free Language

Definition

A formal language is context-free if it is accepted by a pushdown automata.

Properties

Every regular language is context-free, but some context-free languages (e.g., $\{0^n{1}^n\mid n\ge 0\}$) are not regular: $\{L.\exists M:DFA.\mathcal{L}(M)=L\}⊊\{L.\exists M:PDA.\mathcal{L}(M)=L\}$ Equivalently to the main definition a language $L$ is context-free iff by a context-free grammar).

See also

Regular Language Regular Expression Formal Language Chomsky Hierarchy