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.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!