Context-Free Languages

Mort Yao

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

  1. \(V\) is a finite set called the variables,
  2. \(\Sigma\) is a finite set called the terminals, (\(\Sigma \cap V = \emptyset\))
  3. \(R \subseteq V \times (V \cup \Sigma)^*\) is a finite set of substitution rules,
  4. \(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

  1. \(Q\) is a finite set called the states,
  2. \(\Sigma\) is a finite set called the input alphabet,
  3. \(\Gamma\) is a finite set called the stack alphabet,
  4. \(\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\}\))
  5. \(q_0 \in Q\) is the start state,
  6. \(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

  1. \(r_0 = q_0\) and \(s_0 = \varepsilon\),
  2. 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^*\).
  3. \(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:

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