# Context-Free Languages

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