Context-Free Grammar (CFG) Example: Complement of 0^n1^n2^n

Here we create a context-free grammar (CFG) for the complement of the language of all strings of the form 0^n 1^n 2^n. The original (non-complemented) language is famously not context-free, so there has to be special properties of the complemented version that we have to take advantage of. I just give a brief sketch of the grammar in this video, because the grammar is somewhat large, repetitive, and most of what isn't shown is either (1) an almost copy of something else I show, or (2) is regular, which is not that interesting since it is already context-free.

▶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.

[muhammed]

I love this but I can't make a pda for the life of me

[susantasamanta]

Please note that {0^n 2^n 1^n: n>=0} (or {1^n 0^n 2^n: n>=0} or {2^n 1^n 0^n: n>=0} or ...) is also in the complement of {0^n 1^n 2^n: n>=0}. Here you are not considering that ccases.