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.

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 = 0n1n where n>=1
    9. CFG for the language L = 0n12n where n>=1
    10. Write a CFG for the language L = 0n14n where n>=1
Prof.Fazal Rehman Shamil (Available for Professional Discussions)
1. Message on Facebook page for discussions,
2. Video lectures on Youtube
3. Email is only for Advertisement/business enquiries.