Context-Free Grammar

languages

Definition

Context-Free Grammar

A grammar $G=(N,T,P,S)$ is called context-free if every production rule in $P$ is context-free.

Equivalently: A language is called context-free there exists a pushdown automaton that accepts it.

Production

Equivalence

All production variants below yield the same generated language.

Leftmost Production

Leftmost production is process of iteratively replacing the leftmost non-terminal symbol by applying the respective production rules.

Rightmost Production

Rightmost production is process of iteratively replacing the rightmost non-terminal symbol by applying the respective production rules.

Parallel Production

Parallel production is process of iteratively replacing the all non-terminal symbols by applying the respective production rules.

Trees

A context-free grammar can also be represented by a derivation tree. The front of the tree is the word obtained by reading the leaf labels from left to right.

Derivation tree for $aabb$

Consider the context-free grammar

$$G=(\{S\},\{a,b\},\{S\to aSb,S\to ab\},S)$$

A derivation tree for $aabb$ is:

The front of the tree is the word obtained by reading the leaf labels from left to right.

Examples

Grammar for $\{a^m+b^n=c^{m+n}\mid m,n\ge 0\}$

Consider the context-free grammar

$$G=(\{S,T\},\{a,b,c,+,=\},P,S)$$

where the production rules are

$$P=\{S\to aSc\mid +T,T\to bTc\mid =\}$$

Then, for example,

$$aa+bb=cccc\in L(G).$$

A production is:

$$\begin{array}{rl}S& \Rightarrow aSc\\ & \Rightarrow aaScc\\ & \Rightarrow aa+Tcc\\ & \Rightarrow aa+bTccc\\ & \Rightarrow aa+bbTcccc\\ & \Rightarrow aa+bb=cccc\end{array}$$

Palindrome over $\{a,b\}$

Consider the context-free grammar

$$G=(\{S\},\{a,b\},P,S)$$

where

$$P=\{S\to \epsilon \mid aSa\mid bSb\}$$

Then

$$L(G)=\{\epsilon ,a,b,aa,bb,aaa,aba,bab,bbb,\dots \}$$

Even length with middle separator

Let

$$L=\{w\in \{a,b{\}}^{\ast }\mid |w{|}_a=2\cdot |w{|}_b\}$$

Then a context-free grammar for $L$ is

$$G=(\{S\},\{a,b\},P,S)$$

with

$$P=\{S\to aSaSbS\mid aSbSaS\mid bSaSaS\mid \epsilon \}$$

Grammar from Language

Let $L$ be

$$L=\{p{b}^{2k}q\mid p,q\in \{a,c{\}}^{\ast },|p|\ge |q|,k\ge 1\}$$

The context-free grammar for $L$ is given by

$$G=⟨\{S,T,U\},\{a,b,c\},P,S⟩$$

where $P$ and $S$ are defined as:

$$\begin{array}{rl}S& \to US\mid USU\mid T\\ U& \to a\mid c\\ T& \to bb\mid bbT\end{array}$$

For instance, $w=aabc\in L$ can be derived as follows:

$$\begin{array}{rl}S& {\Rightarrow }_{P}US\\ & {\Rightarrow }_{P}aUSU\\ & {\Rightarrow }_{P}aaTc\\ & {\Rightarrow }_{P}aabbc\end{array}$$