% Context-Free Languages
% Mort Yao
% 2017-04-11

**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$.