Last updated on:May 26th, 2018,

Context Free Grammar CFG for language of all even length strings

What is Context Free Grammar CFG for language of all even length strings?

 

S ⇒ aSa |  bSb | aSb | bSa |ε

Now we can read any kind of even length string.

For example;

To read aa from S ⇒ aSa |  bSb | aSb | bSa |ε

S ⇒ aSa 

S⇒aεa

S⇒aa

 

To read abba a from S ⇒ aSa |  bSb | aSb | bSa |ε

S ⇒ aSa

S ⇒ abSba

S⇒ abεba

S⇒ abba

 

To read baab a from S ⇒ aSa |  bSb | aSb | bSa |ε

S ⇒ bSb

S ⇒ baSab

S⇒ baεab

S⇒ baab

 

To read babb a from S ⇒ aSa |  bSb | aSb | bSa |ε

S ⇒ bSb

S ⇒ baSbb

S⇒ baεbb

S⇒ babb

 

To read bbaa a from S ⇒ aSa |  bSb | aSb | bSa |ε

S ⇒ bSa

S ⇒ bbSaa

S⇒ bbεaa

S⇒ bbaa

and similarly we can read even length strings from this CFG.

0Shares

Leave a Reply

Your email address will not be published.