CFG for the language of all non Palindromes

By: Prof. Dr. Fazal Rehman | Last updated: December 28, 2023

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

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 = 0ⁿ1ⁿ where n>=1
9. CFG for the language L = 0ⁿ1²ⁿ where n>=1
10. Write a CFG for the language L = 0ⁿ1⁴ⁿ where n>=1
11. CFG for {aⁿ b aⁿ⁺¹ | n >=0}
12. CFG for {aⁿ b aⁿ⁺² | n >=0}
13. CFG for {aⁿ b aⁿ⁺³ | n >=0}