Design Context Free Grammar Example 1

In this class, We discuss Design Context Free Grammar Example 1.

For Complete YouTube Video: Click Here

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

We discussed about the language L = {aⁿbⁿ where n >= 0}.

Now we do some more practice examples.

Example 1:

Design CFG for a language which accepts palindrome over an alphabet Σ = {a,b}.

Example palindrome: ababa or abba.

Palindrome means the reverse of a string should be the same as string.

Let’s refresh the example L = {aⁿbⁿ where n >= 0} once.

The CFG for L is S – aSb | ε.

Take input aaabbb.

The production S is checking for first a and the last b.

The second expansion of S will check for a second a and last before b.

Based on the above understanding, we write CFG for language palindrome.

The below CFG shows the grammar for palindrome.

S – aSa

S – bSb

S – a | b | ε

Why have we written the above grammar?

Take example ababa.

The first symbol is a, and the last symbol is a.

The second symbol is b, and the last before symbol is b.

We stop by taking a or b or ε.

So we have written the above productions.

The below diagram shows the derivation tree for the input string abba.

Example 2:

Design CFG for a language not accepting palindromes.

Take an example input abaaabbbba.

Take the example of the palindrome.

If the first symbol is a, the last symbol should be a.

If the second symbol is b, the last before symbol should be b.

Take the third symbol is a, but from the last, the third symbol is b.

If we find a situation where it does not match, we can say it is not a palindrome.

The below grammar shows the CFG for not accepting palindrome.

S – aSa | bSb

S – A

A – aBb | bBa

B – aB | bB | ε

if we encounter nonmatching. No need to check the remaining symbols.

We can say the input is not a palindrome.

So we are taking the extra symbol A to check the nonmatching option and calling the nonterminal B

The nonterminal B will take any input and accept.