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

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?

-
You could also construct a pushdown automaton that accepts all and only the strings in the language. –  Rick Decker Oct 3 '12 at 20:28

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

-
+1. Nice, especially for a succinct representation of case (1). –  Rick Decker Oct 4 '12 at 0:46

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

-
It doesn't. Your CFG does not accept, for example, 0101, which is a member of the language requested. –  Paul Z Oct 3 '12 at 23:19