contextfreeness

Contextfreeness is the property of a language being context-free. A language L over an alphabet Σ is context-free if there exists a context-free grammar G with start symbol S such that the strings derivable from S are exactly L. Equivalently, L can be recognized by a nondeterministic pushdown automaton. In the Chomsky hierarchy, context-free languages are Type-2 languages.

Context-free grammars can generate many structured languages, such as balanced parentheses, strings of the form a^n b^n, and palindromes over a finite alphabet. The language { w w^R | w ∈ {a,b}* } is context-free and can be described by a grammar that enforces matching ends around a central point.

Contextfreeness is preserved under operations such as union, concatenation, and the Kleene star, as well as under homomorphism and inverse homomorphism. It is not closed under intersection or complement in general, though intersection with a regular language preserves context-freeness.

Decision problems for context-free languages are well studied. The membership problem is decidable, and parsing can be done in polynomial time (for example, CYK parsing runs in O(n^3) for grammars in Chomsky normal form). Emptiness and finiteness are decidable, but equivalence and containment between two context-free languages are, in general, undecidable.

Contextfreeness is central to formal language theory and the design of programming languages, where grammars specify syntax. It is distinct from broader classes such as context-sensitive and recursive enumerable languages.