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.

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