CFG for the language of all non- Palindromes.
Y→aYa|bYb|aZb|bZa
Z→aZ|bZ|ϵ
Strings that must be accepted
We are testing with some of the strings, you can try it on more strings.
Strings of length 1: {no string}
Strings of length 2: {01,10, no morestring}
Strings of length 3: {001, 011, 100, no more strings }
Strings of length 5: {00001, 00011, 00111, 01111, 10000, 11000, 11100, 11110. no more strings }
Strings of length 8: {01001011, ….. and many more similar strings}
Strings that must be rejected
We are testing with some of the strings, you can try it on more strings.
Strings of length 1: {0, 1}
Strings of length 2: {00,11, no morestring}
Strings of length 5: {10001, 11011, ….. and many more similar 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