Context Free Grammar Examples

In this class, We discuss Context-Free Grammar Examples.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of context-free grammar. Click Here.

Take a language L = {aⁿbⁿ where n >= 0}

L = {ε, ab, aabb, . . .}

The above language is not regular.

We can write context-free grammar for the language L.

We call the language L context-free language.

The below grammar shows the context-free grammar for the language L.

S – aSb

S – ε

We have given a programmatic intuition for expanding grammar. Click Here.

The production S is checking for input symbol a and expanding S.

After completing production S then we check for input symbol b.

The below function is the programmatic intuition for production S.

The function S will check for input symbol a.

if the input symbol is a., Then call the function S.

It is precise as recursion.

After completing the function, call S. We will check for input symbol b.

The production S is checking for every a. we need a matching b.

Take an input string aaabbb.

The below diagram shows the expansion of context-free grammar for the input string aaabbb.

We start with S.

We expand S as aSb.

Again S is expanded as aSb.

We do the expansion of S three times to check the input symbol three times.

The final S is taking epsilon, and the final S is finished. Know the production S will check for b’s.

Take one more string aaabb.

The below expansion is failed to accept the string.

Example 2:

Take a language L1 = {aⁿb²ⁿ where n >= 0}

L1 = {ε, abb, aabbbb, . . .}

The below grammar shows the context-free grammar for the language L1.

S – aSbb

S – ε

Take an input string aabbbb.

The below diagram shows the expansion of grammar for input string aabbbb.