Is the only way to prove that this language is context-free to construct a Context-Free Grammar that accepts it?
If so any hints on how to get started?
Is the only way to prove that this language is context-free to construct a Context-Free Grammar that accepts it?
If so any hints on how to get started?
HINT: Let $L=\{0,1\}^*\setminus\{0^i1^i:i\ge 0\}$. Then $L$ consists of all words of the following three kinds:
It’s not hard to write context-free grammars for each of these types, and once you have them, it’s not hard to combine them into a single context-free grammar that generates $L$.
What do you think about the following? Does it work? $$S\to M1X$$ $$S\to X0M$$ $$M\to 0M1$$ $$M\to \Lambda$$ $$X\to 1X$$ $$X\to 0X$$ $$X\to \Lambda$$