There are four important components in a grammatical description of a language:

- There is a set of symbols that form the strings of the language being defined. They are called terminal symbols, represented by V
_{t}. - There is a finite set of variables, called non-terminals. These are represented by V
_{n}. - One of the variable represents the language being defined; it is called the start symbol. It is represent by S.
- There are finite set of rules called productions that represent the recursive definition of a language. Each production consists of:
- A variable that is being defined by the production. This variable is often called the head of the production.
- The production symbol ->.
- A string of zero or more terminals and variable.

**Formal definition**

A context-free grammar (CFG) is a 4-tuple G=(V_{n}, V_{t}, S, P), where V_{n} and V_{t} are disjoint finite sets, S is an element of V_{n}, and P is a finite set of formulas of the form A -> α, where A ϵ V_{n} and α ϵ (V_{n} U V_{t})*.

**Iterative Derivation**

If α -> β is a production of P in CFG and a and b are strings in (V_{n}, V_{t})*, then

Aαb =>_{G} aβb

We say that the production α -> β is applied to the string aαb to obtain aβb or we say that aαb directly drives aβb.

Now suppose α_{1}, α_{2}, α_{3}, …., α_{m} are string in (V_{n} U V_{t})*,

m >= 1 and α_{1} =>_{G} α_{2}, α_{2} =>_{G} α_{3}, …., α_{m-1} =>_{G}α_{m}

Then we say that α_{1} =>_{G}^{*} α_{m}, i.e. , we say α_{1}, derives α_{m} in grammar G. If α derives β by exactly i steps, we say α=>_{G}^{i} β.

**The Language Generated by a CFG**

Let G = (V_{n}, V_{t}, S, P) be a CFG. The language generated by G is

L(G) = {x ϵ Σ* | S =>_{G}^{*}x}

A language L is a context-free language(CFL) if there is a CFG G so that L = L(G).

**Bacos Naur Form (BNF)**

CFGs are generally written in BNF. In this notation we combine multiple productions with same non-terminal on the left hand side as follows:

S -> bA/aB

**Note:** We always begin with the start symbol S.

**Example:**Write a CFG for the language

L = {wcw^{r} | w ϵ (a, b)*}

Solution

_{n}, V

_{t}, P, S)

Here, V

_{n }= {S}

V

_{t}= {a, b, c}

And P is given by

S -> aSa

S -> bSb

S -> c

Let us check that abbcbba can be derived from the given CFG.

S =>aSa (use the production S -> aSa)

=> abSba (use S -> bSb)

=> abbSbba (use S ->bSb)

=> abbcbba (use S->c)

So string abbcbba can be derived from given CFG.

**Eample 2:**Write a CFG for the regular expression r = 0*1(0+1)*

Solution

Let the CFG be G = (V

_{n}, V

_{t}, P, S)

Here, V

_{n }= {S, A, B}

V

_{t}= {0, 1}

And productions P are defined as

S -> A1B

S -> 0A/ϵ

S -> 0B/1B/ϵ

Let us test the grammar against an example : 001011

S => A1B

=> 0A10B

=> 00A101B

=> 001011

**Question 1: Write a CFG, which generates palindrome for binary numbers.**

Solution

Let G be the CFG G = (V

_{n}, V

_{t}, P, S)

V

_{n}= {S}

V

_{t}= {0, 1}

And production rule P is defined as

S -> 0S0/ 1S1

S -> 0/1/ϵ

**Question 2: Write a CFG for language L = {0 ^{i}1^{j}2^{k} | k <= i or k <= j}**

Solution

L = L

_{1}U L

_{2}

Where L

_{1}= {0

^{i}1

^{j}2

^{k}| k <= i} And L

_{1}= {0

^{i}1

^{j}2

^{k}| k <= j} Let us assume that CFG for L

_{1}is G

_{1}

G

_{1}= (V

_{n}, V

_{t}, P

_{1}, S

_{1})

V

_{n}= {S

_{1}, X, Y}

V

_{t}= {0, 1}

And P

_{1}is defined as

S

_{1}-> S

_{1}2/0Y2

Y -> C/0Y/ϵ

C -> 1C/ϵ

Let us assume that CFG for L

_{2}is G

_{2}

G

_{2}= (V

_{n}, V

_{t}, P

_{2}, S

_{2})

V

_{n}= {S

_{2}, A, B}

V

_{t}= {0, 1}

And P

_{2}is defined as

S

_{2}-> AB

A -> 0A/ϵ

B -> 1B2/1B/ϵ

We can define CFG for L(since L = L

_{1}U L

_{2})

Let us assume that CFG for L is G

G

_{}= (V

_{n}, V

_{t}, P , S)

V

_{n}= { S

_{1}, S

_{2}, X, Y, A, B}

V

_{t}= {0, 1}

P is defined as

S -> S

_{1}/S

_{2}

S

_{1}-> S

_{1}2/0Y2

Y -> C/0Y/ϵ

C -> 1C/ϵ

S

_{2}-> AB

A -> 0A/ϵ

B -> 1B2/1B/ϵ

**Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.**

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.