# Context-Free Languages

Mort Yao**Context-free grammar (CFG).** A *context-free grammar* \(G\) is a 4-tuple \((V, \Sigma, R, S)\), where

- \(V\) is a finite set called the
*variables*, - \(\Sigma\) is a finite set called the
*terminals*, (\(\Sigma \cap V = \emptyset\)) - \(R \subseteq V \times (V \cup \Sigma)^*\) is a finite set of
*substitution rules*, - \(S \in V\) is the
*start variable*.

Given \(u, v, w \in (V \cup \Sigma)^*\), and \(A \mapsto w\) is a substitution rule, we say that \(uAv\) *yields* \(uwv\), denoted as \(uAv \Rightarrow uwv\).

Moreover, given \(w_0, w \in (V \cup \Sigma)^*\), if \(w_0 = w\) or if there exists a sequence \(w_1, \dots, w_k\) (where \(k \geq 0\), and \(\forall 1 \leq i \leq k : w_i \in (V \cup \Sigma)^*\)) such that \(w_0 \Rightarrow w_1 \Rightarrow \dots \Rightarrow w_k \Rightarrow w\), we say that \(w_0\) *derives* \(w\), denoted as \(w_0 \Rightarrow^* w\); the sequence is called a *derivation*. A derivation is a *leftmost derivation* if at every step the leftmost remaining variable is replaced. The leftmost derivation of a string corresponds to the pre-order traversal of its *parse tree*.

\(L\) is the *language of grammar* \(G\), denoted as \(\mathcal{L}(G) = L\), if and only if \(L = \{ w \in \Sigma^*\ |\ S \Rightarrow^* w \}\). We say that the grammar \(G\) *generates* the language \(L\).

**Context-free language (CFL).** A language \(L\) is called a *context-free language* if there exists a CFG \(G\) that generates \(L\).

A grammar \(G\) is said to be *ambiguous*, if there exists a string \(w \in \mathcal{L}(G)\) with two or more leftmost derivations.

**Chomsky normal form (CNF).** A CFG is in *Chomsky normal form* if every substitution rule is of the form \[\begin{aligned}
A &\mapsto BC \\
A &\mapsto a \\
S &\mapsto \varepsilon
\end{aligned}\] where \(A, B, C \in V\), \(B \neq S\), \(C \neq S\), and \(a \in \Sigma\).

**Theorem 1.** Every context-free language is generated by a CFG in Chomsky normal form. (Alternatively: any CFG can be converted into Chomsky normal form that generates the same language.)

**Theorem 2. (Closure properties)** The class of context-free languages is closed under regular operations (i.e., union, concatenation and Kleene star).

**Nondeterministic pushdown automaton (PDA).** A *nondeterministic pushdown automaton* \(M\) is a 6-tuple \((Q, \Sigma, \Gamma, \delta, q_0, F)\), where

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

We say that the PDA \(M = (Q, \Sigma, \Gamma, \delta, q_0, F)\) *accepts* a string \(w\) if \(w\) may be written as \(w = a_1 \cdots a_n\) (where each \(a_i \in \Sigma_\varepsilon\)), and there exists a sequence of states \(r_0, \dots, r_n\) (where each \(r_i \in Q\)) and a sequence of strings \(s_0, \dots, s_n\) (where each \(s_i \in \Gamma^*\)), such that

- \(r_0 = q_0\) and \(s_0 = \varepsilon\),
- For every \(0 \leq i < n\), \((r_{i+1}, \beta) \in \delta(r_i, a_{i+1}, \alpha)\), where \(s_i = \alpha t\) and \(s_{i+1} = \beta t\) for some \(\alpha, \beta \in \Gamma_\varepsilon\) and \(t \in \Gamma^*\).
- \(r_n \in F\).

Otherwise, we say that the PDA \(M\) *rejects* the string \(w\).

\(L\) is the language of PDA \(M\), denoted as \(\mathcal{L}(M) = L\), if and only if \(L = \{w\ |\ w \text{ is a string accepted by } M\}\). We say that the PDA \(M\) *recognizes* the language \(L\).

**Theorem 3.** A language \(L\) is context free if and only if there exists a PDA \(M\) that recognizes \(L\).

**Theorem 4.** Every regular language is context free.

**Theorem 5. (Pumping lemma)** If \(L\) is a context-free language, then there is a number \(p\) (called the *pumping length*) such that if \(w \in L\) and \(|w| \geq p\), then \(w\) may be written as \(w = uvxyz\), under the following conditions:

- For every \(i \geq 0\), \(uv^ixy^iz \in L\),
- \(|vy| > 0\),
- \(|vxy| \leq p\).