I am having issue with designing contex free grammar for the following language:

$L = \{0^n 1^m \, | \, 2n \leq m \leq 3n \}$

I can design for the individual cases i.e. for $m \geq 2n$ and $m \leq 3n$ but don't know how should i combine both. Or is it a different approach altogether?


migrated from cstheory.stackexchange.com Oct 18 '12 at 13:08

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 2
    $\begingroup$ Hint: start from the grammar that generates $0^n1^{2n}$ and add another non terminal symbol at the end that can produce ...... (complete by yourself). $\endgroup$ – Vor Oct 18 '12 at 13:33

It has been a while, since I have done context-free grammars, but I think this should be the answer:

$\qquad \displaystyle A \to 0A11 \mid 0A111 \mid \varepsilon$

I am assuming that empty string is in $L$.

The idea behind is, that you are working your way from outside. Since you need at least 2 times more of $1$'s, than you need $0$'s, you need the first rule. The upper limit is handled with the second rule. All cases inbetween are also covered. $-$ is needed for termination.


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.