# Context Free Grammar - Automata

**Context Free Grammar**

**Grammar** defines a set of rules, and with the help of these rules valid sentences in a language are constructed. A grammar consists of collection of substitution rules, which are also called **production rules.**

**Context Free Grammar **have recursive structure. The language that is associated with Context Free Grammar is called **Context Free Language**. Context Free Grammar has one condition for production rules, i.e., *on the left-hand side of each rule there must be only single variable, and on the right-hand side, there may be combination of variables and terminals including **?.*

The **variables** are those symbols that can be replaced with other variables, terminals, both or ?.

The **terminals** are those symbols which cannot be replaced by anything.

**Example of ****Context free Grammar:**

S -> 0S1

S -> 0

S-> ?

The above given grammar can also be written as:

S -> 0S1|0| ?

If the same variable is given more than one on the left-hand side then we can combine their resulting strings in one line using symbol **“|”**. The sequence of substitutions for obtaining a string is called **derivation**.

**The reverse substitution is not permitted.**

**Example:** S -> 0 is a production, then we can replace S by 0 but not 0 with S.

**Formal Definitions of Context Free Grammar**

Context Free Grammar has 4 tuples (V, T, P, S)

**V: - **V is a finite set of variables also called **non-terminals.**

**T: - **T is a finite set of symbols called terminals that form the strings of the language generated by the grammar.

**P: - **P is a finite set of rules called production rules, each rule have a single variable on the left – hand side and strings of variables and terminals on right hand side.

**S: - **S is a special symbol called the start symbol.

Let us take some examples of Context Free Grammar

**Example1:**

Construct Context Free Grammar to generate the following language.

L = {ww^{R}: w ? {0, 1}*}

**Solution:**

The type of strings that language L generates includes {010010, 110011, 01111110 …..}

Let G = (V, T, P, S) be a context free grammar generating given language

Where V = {S}

T = { 0, 1, ? }

S is the start symbol

P is set of production rules defined as follows:

S -> 0S0

S -> 1S1

S-> ?

Now let us check whether the Context Free Grammar generates the strings that belongs to given language. Consider the string 001100 ? L. The derivations of this string are:

S => 0S0

=> 00S00

=> 001S100

=> 001100

**Thus 001100 ****? L.**

**Example 2:**

Construct Context Free Grammar to generate the following language.

L = {01(1100)^{ n}110 (10)^{ n} | n>=0}

**Solution:**

The type of strings that language L generates includes {01110, 01110011010…..}

Let G = (V, T, P, S) be a context free grammar generating given language

Where V = {S, A, B}

T = {0, 1, ?}

S is the start symbol

P is set of production rules defined as follows:

S -> 01A

A -> 11B0

B -> 00A1

B-> ?

Now let us check whether the Context Free Grammar generates the types of strings that belongs to given language. Consider the string 01110011010 ? L. The derivations of this string are:

S => 01A

=> 0111B0

=> 011100A10

=> 01110011B010

=> 01110011010

**Thus ****01110011010**** ****? L.**

**Example 3:**

Construct Context Free Grammar that generates strings over {0, 1} which contains at least four consecutive 0’s.

**Solution:**

The type of strings that language L generates includes {00001, 110000, 0000, 11010001 …..}

Let G = (V, T, P, S) be a context free grammar generating given language.

Where V = {S, A}

T = {0, 1, ?}

S is the start symbol

P is set of production rules defined as follows:

S -> A0000A

A -> 0A

A -> 1A

A -> ?

Now let us check whether the Context Free Grammar generates the types of strings that belongs to given language. Consider the string 11010001 ? L. The derivations of this string are:

S => A0000A

=> 1A0000A

=> 11A0000A

=> 110A0000A

=> 1101A0000A

=> 11010000A

=> 110100001A

=> 110100001

**Thus 110100001 ? L.**