Prove $\{0,1\}^* -\{0^i 1^i\mid i \ge 0\}$ is context free?

Question

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?

Answer 1

HINT: Let $L=\{0,1\}^*\setminus\{0^i1^i:i\ge 0\}$. Then $L$ consists of all words of the following three kinds:

1. any word of the form $x10y$, where $x,y\in\{0,1\}^*$;
2. any word of the form $0^i1^k$ with $i<k$; and
3. any word of the form $0^i1^k$ with $i>k$.

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

Answer 2

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$$