# Need to give a CFG for this language?

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?

• Is this supposed to be the same language as here? – Raphael Mar 10 '16 at 15:08
• – D.W. Mar 10 '16 at 19:27
• @bobafro Are you sure it is OR in the language and not AND? – Shreesh Mar 11 '16 at 2:27
• It is supposed to be or, yes. – 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$

• 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). – Yuval Filmus Mar 10 '16 at 11:58
• Sorry, for the silly mistake, I did not correctly see the problem. – Shreesh Mar 10 '16 at 12:49
• I am surprised, who gave this answer -1, without asking for an explanation, or without telling what is wrong in this answer. – Shreesh Apr 29 '16 at 14:07
• @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. – Rick Decker Apr 29 '16 at 18:38
• @RickDecker, Thank you, I was just surprised who thought that such an obvious answer is wrong. – Shreesh Apr 30 '16 at 12:18