# Is this language context-free or not?

I have a problem to solve, the problem is:

Is the language of strings

$$L=\{0^x1^y:x\nmid y\}$$

context free?

I suspect it isn't, I spent some time trying to make a grammar that could generate that language, but I couldn't and I don't know how to prove it.

• I think one can use Parikh's theorem to show that this is not context-free, maybe that helps. Apr 23 '15 at 3:34

$S \rightarrow 1 S$
$1S \rightarrow S0$
$S0 \rightarrow \emptyset$