I have the language:

$$ L = \{0^m1^n \mid 0 ≤ m ≤ n\text{ or }0 ≤ n ≤ 2m\}. $$

My goal is to give an equivalent context-free grammar for this language, but I am unsure if I am going about it the right way. So far this is what I've come up with:

$$ \begin{align*} &S \to A \mid X \\ &A \to 0A1 \mid A1 \mid \varepsilon \\ &X \to 00A1 \mid 00A \mid \varepsilon \end{align*} $$ Is this anywhere close?

  • $\begingroup$ Is this supposed to be the same language as here? $\endgroup$ – Raphael Mar 10 '16 at 15:08
  • $\begingroup$ See cs.stackexchange.com/q/18524/755 $\endgroup$ – D.W. Mar 10 '16 at 19:27
  • $\begingroup$ @bobafro Are you sure it is OR in the language and not AND? $\endgroup$ – Shreesh Mar 11 '16 at 2:27
  • $\begingroup$ It is supposed to be or, yes. $\endgroup$ – bob afro Mar 11 '16 at 2:58

Yes it is pretty close but a little far, correct solution will be (if you go about writing grammar methodically)

$S \rightarrow A \ | \ B$
$A \rightarrow 0A1\ |\ A1 \ |\ \epsilon$
$B \rightarrow 0B11\ |\ 0B \ |\ \epsilon$

Otherwise, if you go by logic, condition $0 \leq m \leq n$ OR $0 \leq n \leq 2m$ is true for every non-negative integer pair $m$ and $n$ (because $m \leq n$ OR $n \leq m$ translates to $m \leq n$ OR $n \leq m \leq 2m$, which is always true). Hence your language is really $\{0^m1^n\ |\ m\geq 0, n\geq 0\}$ and the grammar is:

$S \rightarrow 0S \ | \ S1 \ | \ \epsilon$

  • $\begingroup$ Your grammar generates $\{0^m 1^n \mid m \leq n \leq 2m\}$. This is not quite what the OP is after (you have AND whereas OP has OR). $\endgroup$ – Yuval Filmus Mar 10 '16 at 11:58
  • $\begingroup$ Sorry, for the silly mistake, I did not correctly see the problem. $\endgroup$ – Shreesh Mar 10 '16 at 12:49
  • 1
    $\begingroup$ I am surprised, who gave this answer -1, without asking for an explanation, or without telling what is wrong in this answer. $\endgroup$ – Shreesh Apr 29 '16 at 14:07
  • $\begingroup$ @Shreesh. You'll just make your self crazy worrying about such things. Accept the fact that you'll occasionally get random unexplained downvotes. I'll counter the downvote as a favor. $\endgroup$ – Rick Decker Apr 29 '16 at 18:38
  • $\begingroup$ @RickDecker, Thank you, I was just surprised who thought that such an obvious answer is wrong. $\endgroup$ – Shreesh Apr 30 '16 at 12:18

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.