Design Context Free Grammar Examples 2

In this class, We discuss Design Context Free Grammar Examples 2.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of previous examples. Click Here.

Example 1:

Language l1 = {0^n1^(n+1) where n >= 0}.

L1= { 1,011, 00111, . . .}

The language L1 will have a strings sequence of zeros followed by a sequence of one’s.

The number of one’s must be one greater than the number of zero’s.

The below grammar shows the CFG for the language L1.

S – A1

A – 0A1

A – ε

The production S is checking for an extra 1.

First, we call the non-terminal A.

The production A will check for zero’s followed by an equal number of one’s.

After finding an equal number of one’s, the production S will check for an extra 1.

Example 2:

Language L2 = {a^mb^n where m not equal to n, m >= 0, n>=0}

the language L2 will not accept strings containing a’s followed by an equal number of b’s.

The below grammar shows the CFG for language L2.

S – aSb

S – A

S – B

A – aA | a

B – bB | b

We need to find strings containing a’s followed by b’s. But not equal a’s and b’s.

We should find atleast one extra a or one extra b.

The production S will check for a’s followed by an equal number of b’s.

We should not end the production S. We need to check for atleast one extra a or one extra b.

Tho check for extra a’s, we are using production A.

To check for extra b’s, we use production B.

Example 3:

Language L3 = {a^mb^n where n>m, m >= 1, n>=1}

The language L3 similar to language L2.

The condition n>m says we need more number of b’s.

Similar to example 2, we need to check for extra b’s.

The below grammar shows the CFG for language L3.

S – aSb | aAb

A – bA | b