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

By: Prof. Fazal Rehman Shamil | Whatsapp:+923028700085

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

CFG of odd Length strings

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.