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
-
- Intro to Context Free Grammar with 12 Examples
- CFG of Language of all even and odd length palindromes
- Context Free Grammar CFG for language of all even length strings
- CFG for the language of all non Palindromes
- CFG for strings with unequal numbers of a and b
- CFG of odd Length strings {w | the length of w is odd}
- CFG of Language contains at least three 1’s or three a’s {w | w contains at least three 1’s}
- CFG for the language L = 0n1n where n>=1
- CFG for the language L = 0n12n where n>=1
- Write a CFG for the language L = 0n14n where n>=1