Closure properties-show that language is contextfree

Question

I have a question..Using the closure properties,I have to show that the language $\left \{ w\epsilon \left \{ 0,1 \right \}^{*}:w\neq 0^{m}1^{m},m\geq 0 \right \}$ is contextfree.Could you give me a hint how to start?

Answer 1

In order to show this using closure properties one has to start with at least one language known to be context-free. Here $K = \{ 0^n1^n \mid n\ge 0\}$ is a good choice.

You want to show that the complement of $K$ also is context-free, but alas context-free languages are not closed under complement. We can however write your language as the usion of (1) strings $0^m1^n$ with $n>m$ (2) idem with $n<m$ (3) strings not of the form $0^*1^*$.

Language (3) is regular, languages (1) and (2) can be obtained from $K$ using simple language operations.