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

Comments

comments