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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ for any $a$ generate either one $b$ or two $b$'s. $\endgroup$
    – Ran G.
    Commented Mar 31, 2013 at 7:07
  • 1
    $\begingroup$ see related question cs.stackexchange.com/questions/9831/… or use the search to find others. $\endgroup$
    – Ran G.
    Commented Mar 31, 2013 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
    Commented Mar 31, 2013 at 7:20
  • $\begingroup$ read this answer wil help you if you want I can answer here too $\endgroup$
    – Grijesh Chauhan
    Commented Mar 31, 2013 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
    Commented Mar 31, 2013 at 20:15

2 Answers 2

Reset to default
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$

Improve this answer
$\endgroup$
0
-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}$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.