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.
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.
Негізгі бет Context-Free Grammar (CFG) Example: Complement of 0^n1^n2^n
Пікірлер: 4