Context Free Grammar CFG for language of all even length strings

By Prof. Fazal Rehman Shamil
Last modified on August 25th, 2020

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.

Context Free Grammar CFG for language of all even length a’s defined over {a, b}.

S ⇒ aSa |  bS |ε

valid strings: aa, aba, abba, abaaa, ……and many more similar strings.

invalid strings.

invalid strings: a, ab, abb, aaba, ……and many more similar strings.

invalid strings.

Context Free Grammar CFG for language of all even length b’s defined over {a, b}.

S ⇒ bSb |  aS |ε

CFG for language of all even length a’s defined over {a, b, c}.

S ⇒ aSa |  bS |c S |ε

valid strings: aa, aba, aca, abca, acba, ……and many more similar strings.

invalid strings.

invalid strings: a, ba, ca, abc, acbaa, ……and many more similar strings.

invalid strings.

CFG for language of all even length a’s defined over {a, b, c, d}.

S ⇒ aSa |  bS |cS|dS |ε


Context Free Grammar  for language of all even length 0’s defined over {0, 1}.

S ⇒ 0S0b |  1S |ε

Context Free Grammar  for language of all even length 1’s defined over {0, 1}.

S ⇒ 1S1b |  0S |ε

Prof.Fazal Rehman Shamil (Available for Professional Discussions)
1. Message on Facebook page for discussions,
2. Video lectures on Youtube
3. Email is only for Advertisement/business enquiries.