Context-Free Grammar (CFG) Example: Non-Palindromes
Here we create a context-free grammar (CFG) for the set of strings that do NOT represent palindromes over {0, 1}. The trick with this language is that we know when a string is not a palindrome, namely when the same position from "either end" of the string is different, for some position. For example, 0100 is not a palindrome because two characters from either end give 1 in one case, and 0 in the other. To finish a CFG, we make characters from either end that are the same until we must (at some point) encounter a "bad" pair. After that (in the "middle") there can be literally any character.
Easy Theory Website: https://www.easytheory.org
Discord: / discord
If you like this content, please consider subscribing to my channel: / @easytheory
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.