Context Free Grammar CFG for language of all even length strings

Download This Tutorial in PDF

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 |ε

Subscribe for Friendship

Latest posts by Prof. Fazal Rehman Shamil (see all)

Buy advertisement space on T4Tutorials

For more details email [email protected]