4
$\begingroup$

My problem with CFG is, I am to generally create ones that don't have requirements such as:

$\qquad \{a^m b^n \mid m \le n \le 2m \}$

I have no clue where to begin, and how to approach it. I was wondering if you can provide some hints for such daunting problems, along with how to solve that problem.

This is not homework, this is merely me trying to learn it. I solved many problems that did not have such requirements, but those problem are the ones where I am forced to look at the solution.

$\endgroup$

migrated from cstheory.stackexchange.com Mar 31 '13 at 5:13

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

  • 1
    $\begingroup$ for any $a$ generate either one $b$ or two $b$'s. $\endgroup$ – Ran G. Mar 31 '13 at 7:07
  • 1
    $\begingroup$ see related question cs.stackexchange.com/questions/9831/… or use the search to find others. $\endgroup$ – Ran G. Mar 31 '13 at 7:08
  • 1
    $\begingroup$ If you're more comfortable with PDAs, you can always convert between the two (you get ugly grammars though). Given time, I'll write this out as a proper answer, unless someone else wants to. $\endgroup$ – Luke Mathieson Mar 31 '13 at 7:20
  • $\begingroup$ read this answer wil help you if you want I can answer here too $\endgroup$ – Grijesh Chauhan Mar 31 '13 at 20:07
  • $\begingroup$ I don't understand the problem ... now we know what requirements are not on your CFG, but what are the requirements? $\endgroup$ – user1129682 Mar 31 '13 at 20:15
2
$\begingroup$

Just read the constraint carefully. $m\le n$ tells you that you must have at least as many b's as a's. The other part: $n\le 2m$ tells you that you cannot have more than twice as much a's.

Here is an EBNF description that yon can convert to BNF.

$S\to aSb[b] \mid \epsilon$

$\endgroup$
-2
$\begingroup$

Hint: Each $a$ corresponds to either one $b$ or two $b$s. Form a hybrid between grammars for $a^n b^n$ and $a^n b^{2n}$.

$\endgroup$

Your Answer

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