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.

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

Here's a set of production rules that produce the strings, which seems to fail the Wikipedia definition of context-free grammar.

$S \rightarrow 1 S$

$1S \rightarrow S0$

$S0 \rightarrow \emptyset$

As far as the restriction you mentioned on the produced strings, I don't know how that factors in. Hopefully this can help you.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.