What is Context Free Grammar CFG for the 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 |ε

More Examples of CFG

1. Intro to Context Free Grammar with 12 Examples
2. CFG of Language of all even and odd length palindromes
3. Context Free Grammar CFG for language of all even length strings
4. CFG for the language of all non Palindromes
5. CFG for strings with unequal numbers of a and b
6. CFG of odd Length strings {w | the length of w is odd}
7. CFG of Language contains at least three 1’s or three a’s {w | w contains at least three 1’s}
8. CFG for the language L = 0ⁿ1ⁿ where n>=1
9. CFG for the language L = 0ⁿ1²ⁿ where n>=1
10. Write a CFG for the language L = 0ⁿ1⁴ⁿ where n>=1
11. CFG for {aⁿ b aⁿ⁺¹ | n >=0}
12. CFG for {aⁿ b aⁿ⁺² | n >=0}
13. CFG for {aⁿ b aⁿ⁺³ | n >=0}