Context-Free Languages

Context-Free Grammar (CFG)

In the introduction to automata theory, we saw that finite automata recognize exactly the regular languages. However, many important languages, including the syntax of most programming languages, have recursive, nested structure that regular languages cannot capture. Context-free grammars provide a more powerful formalism for describing such languages.

Definition: Context-Free Grammar (CFG)

A context-free grammar is a 4-tuple $(V, \Sigma, R, S)$ where

$V$ is a finite set called the variables,
$\Sigma$ is a finite set disjoint from $V$, called the terminals,
$R$ is a finite set of production rules, each of the form $A \to w$ where $A \in V$ and $w \in (V \cup \Sigma)^*$,
$S \in V$ is the start variable.

Definition: Derivation and Generated Language

Let $G = (V, \Sigma, R, S)$ be a context-free grammar. For strings $\alpha, \beta \in (V \cup \Sigma)^*$, we say $\alpha$ yields $\beta$ in one step, written $\alpha \Rightarrow \beta$, if there exist $u, v \in (V \cup \Sigma)^*$ and a rule $A \to w \in R$ such that \[ \alpha = uAv \quad \text{and} \quad \beta = uwv. \]

We write $\alpha \Rightarrow^* \beta$ if either $\alpha = \beta$ or there exists a finite sequence \[ \alpha = \alpha_0 \Rightarrow \alpha_1 \Rightarrow \cdots \Rightarrow \alpha_k = \beta \quad (k \geq 1), \] called a derivation of $\beta$ from $\alpha$. The language generated by $G$ is \[ L(G) = \{ w \in \Sigma^* \mid S \Rightarrow^* w \}. \] A language $L \subseteq \Sigma^*$ is context-free if $L = L(G)$ for some context-free grammar $G$.

Example:

\[ \begin{align*} &X \to 00X1 \, | \, Y01 \\\\ &Y \to \$ \end{align*} \] In this grammar, $V = \{X, Y\}, \, \Sigma = \{0, 1, \$\}, \, S = X$, and $R$ is the collection of above rules.

For example, this grammar generates the string $0000\$0111$. The derivation of the string in this grammar is \[ X \Rightarrow 00X1 \Rightarrow 0000X11 \Rightarrow 0000Y0111 \Rightarrow 0000\$0111. \] Here $X \to 00X1 \, | \, Y01$ abbreviates the two rules $X \to 00X1$ and $X \to Y01$.

Context-free grammars are strictly more powerful than regular expressions. Every regular language is context-free, but not vice versa. The key advantage is that CFGs can describe recursive and nested structures.

Consider the language \[ L_1 = \{0^n 1^n \mid n \geq 0\}. \] This language is not regular. No finite automaton can recognize it, because a finite automaton cannot "count" an unbounded number of 0s and then match them with the same number of 1s. To prove this rigorously, we use the Pumping Lemma.

Pumping Lemma

The Pumping Lemma is the standard tool for proving that a language is not regular. The idea is that any sufficiently long string in a regular language must contain a substring that can be "pumped" (repeated any number of times) while remaining in the language. This is a consequence of the pigeonhole principle applied to the finite number of states.

Theorem: Pumping Lemma for Regular Languages

If $L$ is a regular language, then there exists $p \in \mathbb{N}$ (called the pumping length) such that every string $s \in L$ with $|s| \geq p$ can be divided into three pieces, $s = xyz$, satisfying:

$\forall i \geq 0, \, xy^i z \in L$,
$|y| \gt 0$,
$|xy| \leq p$.

Proof Sketch.

Since $L$ is regular, there exists a DFA $M = (Q, \Sigma, \delta, q_0, F)$ recognizing $L$. Set $p = |Q|$. Let $s = s_1 s_2 \cdots s_n \in L$ with $n \geq p$, and let \[ r_0, r_1, \ldots, r_n \] be the sequence of states $M$ visits while reading $s$, where $r_0 = q_0$, $r_i = \delta(r_{i-1}, s_i)$ for $i \geq 1$, and $r_n \in F$.

The sequence $r_0, r_1, \ldots, r_p$ consists of $p + 1$ states drawn from $Q$ (which has only $p$ elements), so by the pigeonhole principle two of them must coincide. Thus there exist indices $0 \leq j \lt k \leq p$ with $r_j = r_k$. Define \[ x = s_1 \cdots s_j, \quad y = s_{j+1} \cdots s_k, \quad z = s_{k+1} \cdots s_n. \] Then $s = xyz$, $|y| = k - j \gt 0$, and $|xy| = k \leq p$.

Reading $x$ takes $M$ from $r_0$ to $r_j$, reading $y$ takes it from $r_j$ back to $r_k = r_j$, and reading $z$ takes it from $r_j$ to $r_n \in F$. Hence for every $i \geq 0$, reading $xy^i z$ loops the cycle $i$ times before continuing along $z$, still ending at $r_n \in F$. Therefore $xy^i z \in L$ for all $i \geq 0$.

To see this concretely, suppose for contradiction that $L_1$ is regular, with pumping length $p$. Choose $s = 0^p 1^p \in L_1$. Since $|s| = 2p \geq p$, the lemma gives a decomposition $s = xyz$ with $|xy| \leq p$ and $|y| \gt 0$. The constraint $|xy| \leq p$ forces $xy$ to lie entirely within the initial block of $0$s, so $y$ consists only of $0$s, say $y = 0^k$ with $k \geq 1$. Then $xy^2 z = 0^{p+k} 1^p$ has more $0$s than $1$s, hence $xy^2 z \notin L_1$, contradicting the first condition of the Pumping Lemma. Therefore $L_1$ is not regular.

However, $L_1$ is context-free. It is generated by the grammar $G$ with start variable $S$ and rules \[ S \to 0S1 \mid \epsilon. \] Indeed, applying the rule $S \to 0S1$ exactly $n$ times followed by $S \to \epsilon$ yields the derivation \[ S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow \cdots \Rightarrow 0^n S 1^n \Rightarrow 0^n 1^n, \] which shows that every $0^n 1^n$ lies in $L(G)$. Conversely, an induction on derivation length shows that every string derivable from $S$ is of the form $0^k S 1^k$ or $0^k 1^k$, so $L(G) \subseteq L_1$.

The recursive rule $S \to 0S1$ ensures that every 0 is matched by a corresponding 1. This is exactly the kind of nested structure that a CFG can capture but a finite automaton cannot.

Pushdown Automata

The Pumping Lemma showed that finite automata lack the memory to handle languages like $L_1 = \{0^n 1^n\}$. To recognize context-free languages, we need a computational model with auxiliary storage. A pushdown automaton (PDA) extends a finite automaton with a stack, an unbounded last-in, first-out memory. The stack provides exactly the right amount of additional power.

Definition: Pushdown Automaton (PDA)

A pushdown automaton is a 6-tuple $(Q, \Sigma, \Gamma, \delta, q_0, F)$ where

$Q$ is a finite set of states,
$\Sigma$ is a finite set called the input alphabet,
$\Gamma$ is a finite set called the stack alphabet,
$\delta: Q \times \Sigma_{\epsilon} \times \Gamma_{\epsilon} \to \mathcal{P}(Q \times \Gamma_{\epsilon})$ is the transition function,
$q_0 \in Q$ is the start state,
$F \subseteq Q$ is the set of accept states.

Here $\Sigma_{\epsilon} = \Sigma \cup \{\epsilon\}$ and $\Gamma_{\epsilon} = \Gamma \cup \{\epsilon\}$, matching the convention in the definition of nondeterministic finite automata. A transition $(r, c) \in \delta(q, a, b)$ means that from state $q$ the PDA may read input symbol $a$ (or no input if $a = \epsilon$), pop $b$ from the top of the stack (or nothing if $b = \epsilon$), move to state $r$, and push $c$ onto the stack (or nothing if $c = \epsilon$). The codomain uses the power set $\mathcal{P}(\cdot)$, reflecting nondeterminism.

Definition: PDA Computation and Acceptance

Let $M = (Q, \Sigma, \Gamma, \delta, q_0, F)$ be a PDA and $w \in \Sigma^*$ an input string. The PDA $M$ accepts $w$ if $w$ can be written as $w = w_1 w_2 \cdots w_m$ with each $w_i \in \Sigma_{\epsilon}$, and there exist a sequence of states $r_0, r_1, \ldots, r_m \in Q$ and a sequence of stack contents $s_0, s_1, \ldots, s_m \in \Gamma^*$ satisfying:

$r_0 = q_0$ and $s_0 = \epsilon$ (the computation starts in the start state with empty stack),
for each $i \in \{0, 1, \ldots, m-1\}$, there exist $b, c \in \Gamma_{\epsilon}$ and $t \in \Gamma^*$ with $s_i = bt$, $s_{i+1} = ct$, and $(r_{i+1}, c) \in \delta(r_i, w_{i+1}, b)$ (each step follows a valid transition: pop $b$, push $c$),
$r_m \in F$ (the computation ends in an accept state).

The language recognized by $M$ is \[ L(M) = \{ w \in \Sigma^* \mid M \text{ accepts } w \}. \]

A PDA is similar to an NFA but can additionally push symbols onto and pop symbols from its stack at each step. This extra memory allows PDAs to recognize some nonregular languages.

Again, consider the language: \[ L_1 = \{0^n 1^n \mid n \geq 0\}. \] The PDA $M_1$ processes its input as follows:

As each $0$ is read, push it onto the stack.
After the $0$s, pop a $0$ off the stack for each $1$ that is read.
Accept if the input ends exactly when the stack becomes empty, and reject otherwise.

We now build the state diagram of the PDA $M_1$ recognizing $L_1$. \[ \begin{align*} &Q = \{q_1, q_2, q_3, q_4\} \\\\ &\Sigma = \{0, 1\} \\\\ &\Gamma = \{0, \$\} \\\\ &F = \{q_1, q_4\} \end{align*} \] Here the special symbol $\$$ serves as a bottom-of-stack marker.

The edge labels have the form $a,\, b \to c$. Such a label means that the machine reads $a$ from the input, pops $b$ from the top of the stack, and pushes $c$ onto the stack. For example, $1,\, 0 \to \epsilon$ means "read a 1, pop a 0, and push nothing" (effectively removing the 0).

Theorem: CFG-PDA Equivalence

A language is context-free if and only if some pushdown automaton recognizes it.

Proof Sketch.

Both directions are constructive. We describe the constructions but omit the inductive verification that they preserve the language.

$(\Rightarrow)$ CFG to PDA.
Given a CFG $G = (V, \Sigma, R, S)$, we build a PDA $P$ that nondeterministically simulates leftmost derivations of $G$. These are derivations in which, at each step, the leftmost variable in the current sentential form is the one expanded. The stack holds the suffix of the current sentential form yet to be matched. The PDA $P$ initially pushes a new bottom-of-stack marker $\$$ and then $S$, and on each step it does one of two things. If the top of the stack is a variable $A$, it pops $A$ and nondeterministically pushes some $w$ such that $A \to w \in R$ (simulating a derivation step, with the symbols of $w$ pushed one per transition through auxiliary states). If the top is a terminal $a$, it pops $a$ and matches it against the next input symbol. When $\$$ reappears on top, $P$ pops it and enters its accept state. Acceptance therefore occurs exactly when the input is consumed and the simulated sentential form is exhausted, which corresponds to a successful derivation of the input from $S$.

$(\Leftarrow)$ PDA to CFG.
Given a PDA $P$, we may assume (after a routine normalization) that $P$ has a single accept state, empties its stack before accepting, and on each transition either pushes one symbol or pops one symbol but not both. We then construct a CFG with variables $A_{pq}$ for each pair of states $(p, q)$, where $A_{pq}$ is intended to generate exactly the strings that can take $P$ from state $p$ with empty stack to state $q$ with empty stack. Production rules are designed to mirror PDA transitions. Suppose that $P$ moves from $p$ to $r$ while reading $x \in \Sigma_{\epsilon}$ and pushing a symbol $u$, and later moves from $s$ to $q$ while reading $y \in \Sigma_{\epsilon}$ and popping the same $u$. This is captured by a rule $A_{pq} \to x A_{rs} y$. Rules $A_{pq} \to A_{pr} A_{rq}$ cover computations whose stack empties at an intermediate state $r$, and rules $A_{pp} \to \epsilon$ cover the empty computation. The start variable is $A_{q_0 q_{\mathrm{accept}}}$, where $q_{\mathrm{accept}}$ is the single accept state.

Moreover, every regular language is context-free, because every regular language is recognized by a finite automaton, and every finite automaton is automatically a pushdown automaton (one that simply ignores its stack).

Non-Context-Free Languages

Just as the Pumping Lemma for regular languages lets us prove that certain languages are not regular, there is an analogous result for context-free languages. This time, two separate pieces of a long string are pumped together.

Theorem: Pumping Lemma for Context-Free Languages

If $L$ is a context-free language, then there exists a pumping length $p \in \mathbb{N}$ such that every string $s \in L$ with $|s| \geq p$ can be divided into five pieces, $s = uvxyz$, satisfying:

$\forall\, i \geq 0, \quad uv^i x y^i z \in L$,
$|vy| \gt 0$,
$|vxy| \leq p$.

Proof Sketch.

Let $G$ be a CFG generating $L$. Convert $G$ to Chomsky Normal Form. In this standard normal form, every production is either $A \to BC$ (with $B, C$ variables other than the start variable) or $A \to a$ (with $a$ a terminal), the only exception being a rule $S \to \epsilon$ for the start variable $S$. In Chomsky Normal Form, every parse tree of a non-empty string is a binary tree whose leaves are terminals.

Let $m$ be the number of variables in $G$, and set $p = 2^{m+1}$. Every node of a parse tree has at most two children, so a parse tree of height $h$ has at most $2^h$ leaves. A parse tree of $s$ with $|s| \geq p$ therefore has height at least $m + 1$, so a longest root-to-leaf path has length at least $m + 1$. Such a path touches at least $m + 2$ nodes, all labelled with variables except the leaf. By the pigeonhole principle, two of its lowest $m + 1$ variable nodes carry the same variable, say $A$.

Let the upper of these two occurrences of $A$ be the root of a subtree deriving the substring $vxy$, and the lower occurrence be the root of a subtree deriving $x$. We decompose $s$ accordingly as $s = uvxyz$. Because the upper $A$ generates $vxy$ and the lower $A$ generates $x$, we may iterate or skip the intervening derivation. Replacing the upper subtree with the lower one yields a parse tree of $uxz$, and replacing the lower subtree with a copy of the upper one $i - 1$ times yields a parse tree of $uv^i x y^i z$ for $i \geq 1$. Hence $uv^i x y^i z \in L$ for all $i \geq 0$, giving condition 1.

Condition 2 ($|vy| \gt 0$) holds because the upper $A$ has a variable below it and is therefore expanded by a rule $A \to BC$. The lower $A$ lies in the subtree of one of $B$ and $C$, and the other one derives a non-empty string, since in Chomsky Normal Form only a start rule produces the empty string. That string is part of $v$ or $y$. Condition 3 ($|vxy| \leq p$) holds because the path is a longest one and the upper $A$ lies among its lowest $m + 1$ variable nodes. The upper-$A$ subtree therefore has height at most $m + 1$, hence at most $2^{m+1} = p$ leaves.

Consider the language \[ L_2 = \{a^n b^n c^n \mid n \geq 0\}. \] This is not a context-free language. Intuitively, recognizing $L_2$ requires maintaining two independent counts simultaneously (matching $a$'s with $b$'s and $b$'s with $c$'s), which exceeds the capability of a single stack.

To make this precise, suppose for contradiction that $L_2$ is context-free, with pumping length $p$. Choose $s = a^p b^p c^p \in L_2$. Since $|s| = 3p \geq p$, the lemma gives a decomposition $s = uvxyz$ satisfying conditions 1-3. The constraint $|vxy| \leq p$ forces $vxy$ to span at most two of the three symbol blocks (since each block has length $p$, and a substring meeting all three contains the whole middle block and has length $\geq p + 2 \gt p$). There are now two cases:

$v$ and $y$ each contain only one symbol type. Then $uv^2 x y^2 z$ increases the counts of at most two of the three symbols $a, b, c$ while leaving the third unchanged, breaking the equality $n_a = n_b = n_c$ required for membership in $L_2$.
$v$ or $y$ contains symbols of more than one type. Then $uv^2 x y^2 z$ places symbols out of the required order $a^* b^* c^*$, again leaving $L_2$.

Either way, $uv^2 x y^2 z \notin L_2$, contradicting condition 1. Hence $L_2$ is not context-free.

Recognizing $L_2$ therefore requires more computational power than a PDA provides. A Turing machine, for instance, can recognize it.

Deterministic Pushdown Automata (DPDAs)

Recall that for finite automata, deterministic (DFA) and nondeterministic (NFA) models recognize the same class of languages, by the NFA-DFA equivalence. For pushdown automata, however, the situation is different. Nondeterministic PDAs are strictly more powerful than deterministic ones. Some context-free languages cannot be recognized by any DPDA.

Nevertheless, deterministic context-free languages (DCFLs), those recognizable by DPDAs, are of great practical importance. Programming-language grammars are typically designed so that their syntax is deterministic context-free, which allows efficient parsers (syntax analyzers) to be constructed for their compilers.

Definition: Deterministic Pushdown Automaton (DPDA)

A deterministic pushdown automaton is a PDA $(Q, \Sigma, \Gamma, \delta, q_0, F)$ whose transition function satisfies $|\delta(q, a, b)| \leq 1$ for every $(q, a, b) \in Q \times \Sigma_{\epsilon} \times \Gamma_{\epsilon}$, together with the following determinism condition: for every $q \in Q$, $a \in \Sigma$, and $x \in \Gamma$, at most one of \[ \delta(q, a, x), \quad \delta(q, a, \epsilon), \quad \delta(q, \epsilon, x), \quad \delta(q, \epsilon, \epsilon) \] is non-empty.

Note that all four may be empty. When no transition is defined for the current configuration, the computation halts, and if input remains unread at that point, the input is rejected. Determinism requires no ambiguity in the next move, not that a next move always exists.

DPDAs still permit $\epsilon$-transitions. The determinism condition requires that at most one transition applies in each situation, not that every transition must read input and stack simultaneously. The following kinds of transition therefore remain available:

$\delta(q, a, \epsilon)$: read input $a$ without inspecting the stack,
$\delta(q, \epsilon, x)$: pop $x$ from the stack without reading input,
$\delta(q, \epsilon, \epsilon)$: neither read input nor inspect the stack.

The language $L_1 = \{0^n 1^n \mid n \geq 0\}$ from our earlier example is a DCFL. The PDA we constructed for it is in fact deterministic, since at each step the current state, input symbol, and top-of-stack symbol uniquely determine the next move.

The three classes form the hierarchy \[ \text{regular languages} \subsetneq \text{DCFLs} \subsetneq \text{CFLs}. \] The inclusion regular $\subseteq$ DCFLs follows by the same idea used earlier for regular $\subseteq$ CFLs. A DFA is automatically a DPDA that ignores its stack. This inclusion is strict because $L_1 = \{0^n 1^n\}$ is a DCFL but, as we showed using the Pumping Lemma, not regular.

The inclusion DCFLs $\subseteq$ CFLs is immediate (every DPDA is a PDA), and is strict as well. A classical example separating the two classes is \[ L_3 = \{w w^{\mathrm{R}} \mid w \in \{0, 1\}^*\} \] (palindromes of even length over $\{0, 1\}$, where $w^{\mathrm{R}}$ denotes the reverse of $w$). A nondeterministic PDA can recognize $L_3$ by guessing the midpoint and matching symbols against the stack. No deterministic PDA can do so, because no fixed strategy can know when the input has reached its midpoint without lookahead. We omit the formal lower-bound argument that no DPDA recognizes $L_3$, since it is delicate and beyond the scope of this page.

Loading...

Context-Free Grammar (CFG)

Pumping Lemma

Pushdown Automata

Non-Context-Free Languages

Deterministic Pushdown Automata (DPDAs)