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

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.

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

    Buy advertisement space on T4Tutorials

    For more details email [email protected]