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$