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