CFG of odd Length strings {w | the length of w is odd}

By: Prof. Dr. Fazal Rehman | Last updated: December 28, 2023

CFG of odd Length strings {w | the length of w is odd}

Context-free grammar for the language of odd length strings is mentioned below;

L = {w | the length of w is odd}:
S → aX | bX
X→ aS | bS | ε

Now we can read any kind of odd length string.

Examples of CFG of odd Length strings

To read a;

CFG:

S → aX | bX
X→ aS | bS | ε

Path to Read the String

S ⇒ aX  //Read first a.

X⇒ε  //Read first aε.

finally, we can read it as a.

Congratulation, the string can be read and the machine can be stoped after successfully completing its task.

To read b;

CFG:

S → aX | bX
X→ aS | bS | ε

Path to Read the String

S ⇒ bX   //Read first b.

X⇒ε  //Read first bε.

finally, we can read it as b.

Congratulation, the string can be read and the machine can be stoped after successfully completing its task.

To read ab;

CFG:

S → aX | bX
X→ aS | bS | ε

Path to Read the String

S ⇒ aX   //Read first a.

X = bS  //Read first ab.

Finally, Read the ab but S is forcing to reading some unknown alphabets.

Oh sorry, the string ab can be read but machine cant stop here because machine again force the CFG to read from S as mentioned in X=bS

To read ba;

CFG:

S → aX | bX
X→ aS | bS | ε

Path to Read the String

S ⇒ bX  //Read first b.

X = aS  //Read the first ba.

Finally, Read the ba but S is forcing to reading some unknown alphabets.

Oh sorry, the string ba can be read but machine cant stop here because machine again force the CFG to read from S as mentioned in X=bS

To read aba;

CFG:

S → aX | bX
X→ aS | bS | ε

Path to Read the String

S ⇒ aX  //Read first a.

X = bS  //Read first ab.

S = aX  //Read first aba.

X = ε  //Read first abaε.

finally, we can read it as aba.

Congratulation, the string can be read and the machine can be stoped after successfully completing its task.

To read babaa;

CFG:

S → aX | bX
X→ aS | bS | ε

Path to Read the String

S ⇒ bX  //Read first b.

X = aS  //Read first ba.

S = bX //Read first bab.

X = aS  //Read first baba.

S = aX  //Read first babaa.

X = ε  //Read first babaaε.

finally, we can read it as babaa.

Congratulation, the string can be read and the machine can be stoped after successfully completing its task.

To read ababb;

CFG:

S → aX | bX
X→ aS | bS | ε

Path to Read the String

S ⇒ aX  //Read first a.

X = bS  //Read first ab.

S = aX //Read first aba.

X = bS  //Read first abab.

S = bX  //Read first ababb.

X = ε  //Read first ababbε.

finally, we can read it as ababb.

Congratulation, the string can be read and the machine can be stoped after successfully completing its task.

Conclusion:

Final CFG of odd Length strings is

S → aX | bX
X→ aS | bS | ε

This CFG can accept all the 100% strings of the mentioned language and rejects the all 100% strings that are not part of the language of odd length strings.

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}