# Context-Free Languages

A context-free grammar is a tuple \(G=(V, \Sigma, P, S)\) where

- \(V\) is a finite set of variables,
- \(\Sigma\) is an alphabet with a finite set of symbols which are called terminals,
- \(P\) is a finite set of production rules, where each rule consists of a variable and a string of variables and terminals,
- \(S \in V\) is the start variable.

Let \(A\) be a variable and \(u,v,w\) be strings of variables and terminals. Given a rule \(A\to w\), we say \(uAv\) yields \(uwv\), and write \(uAv \to uwv\). We also write \(\to^*\) for a sequence of yielding.

A CFG \(G=(V, \Sigma, P, S)\) defines a language

\[

L(G)=\{w\in\sigma^{*}\mid S \to^{*} w \}.

\]

Language defined by context-free grammars is call context-free languages (CFL).

We say a CFG is in the *Chomsky normal form* if every rule is in one of the following forms:

- \(A\to BC\),
- \(A\to a\),
- \(S\to \epsilon\),

where \(A,B,C\) are variables, \(S\) is the start variable, and \(a\) is a terminal.

**Theorem.**

Any CFG is equivalent to a CFG in the Chomsky normal form.

A * pushdown automaton (PDA)* is a tuple \(P=(Q,\Sigma, \Gamma, \delta, q_0, F)\) where:

- \(Q\) is a finite set of states,
- \(\Sigma\) is the input alphabet,
- \(\Gamma\) is the stack alphabet,
- \(\delta\) is the transition function from \(Q\times \Sigma_\epsilon \times \Gamma_{\epsilon}\) to \(2^{Q\times \Gamma_{\epsilon}}\)
- \(q_0\in Q\) is the start state,
- \(F \subseteq Q\) is a set of final states.

**Theorem [CFG = PDA]**

A language is context free iff there exists a pushdown automaton accepts it.

Every regular language is context free.

**The Pumping Lemma.**

For any context-free language \(L\), there exists \(n\) such that for every \(w \in L\) with \(|w|\geq n\), we can divide \(w\) into five parts \(w=uvxyz\) satisfying:

- \(|vy| > 0\),
- \(|vxy| \leq n\),
- \(uv^k x y^k z\in L\), for \(k\geq 0\).