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\).