Context-free language

related topics
{math, number, function}
{language, word, form}
{area, community, home}

In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.

Contents

Examples

An archetypical context-free language is L = \{a^nb^n:n\geq1\}, the language of all non-empty even-length strings, the entire first halves of which are a's, and the entire second halves of which are b's. L is generated by the grammar S\to aSb ~|~ ab, and is accepted by the pushdown automaton M = ({q0,q1,qf},{a,b},{a,z},δ,q0,{qf}) where δ is defined as follows:

δ(q0,a,z) = (q0,a)
δ(q0,a,a) = (q0,a)
δ(q0,b,a) = (q1,x)
δ(q1,b,a) = (q1,x)
δ(q1,λ,z) = (qf,z)

δ(state1,read,pop) = (state2,push)
where z is initial stack symbol and x means pop action.

Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar S\to SS ~|~ (S) ~|~ \lambda. Also, most arithmetic expressions are generated by context-free grammars.

Closure properties

Context-free languages are closed under the following operations. That is, if L and P are context-free languages, the following languages are context-free as well:

Full article ▸

related documents
Euler's theorem
Product of group subsets
Surjective function
Linearity of integration
Online algorithm
List of Fourier-related transforms
The Third Manifesto
Z notation
Group object
De Bruijn-Newman constant
Hurwitz polynomial
Hilbert's Nullstellensatz
Precondition
Rectangle
Constant folding
Discrete mathematics
Conjugate closure
CycL
Sigmoid function
Distinct
Derivative of a constant
Direct sum of groups
RC5
Essential singularity
Greibach normal form
Location parameter
Landau's function
Recursive language
Euler-Jacobi pseudoprime
Star height problem