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.

Fazal Rehman Shamil Click Here to Know More
Instructor, Researcher, Blogger, SEO Expert, Poet and Publisher of International Journal Of Software, Technology & Science ISSN : 2616 - 5325
Dear Professors and Resarchers!You are welome to Cite these tutorials in your research or slides etc. Please don't forget to mention the reference of website. Copy Paste of text is strcitly forbidden. Images can be reuse because images are protected with watermark.

Leave a Reply

Your email address will not be published. Required fields are marked *