2

My problem with CFG is, I am to generally create ones but once they have requirements such as:

$$\{a^m b^n: 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 HW, this is merely me trying to learn it. I solved many problems that did not have such requirements, but those problem with those conditions are the ones where I am forced to look at the solution. A solution that presents the thinking process behind it would help.

Thanks!

Gaak
  • 221
  • It’s very easy to write down an arbitrary context-free grammar, so that can’t be what you’re trying to do, but I don’t see what you are trying to do. Could you explain a bit more clearly? – Brian M. Scott Mar 31 '13 at 00:21
  • @BrianM.Scott I am not able to solve that problem, because of the constraint m<=n<=2M, these constraints where all 3 are dependent on each other boggles my mind, so I was hoping someone can hold my hand and help me understand how to tackle problems of that nature – Gaak Mar 31 '13 at 00:23
  • Ah, I see; it was an English problem. I had the impression that you did not have trouble with that kind of requirement, but in fact that’s the kind with which you do have trouble. One last question: did you really mean $m\le n\le 2m$, not $m\le n\le 2M$? – Brian M. Scott Mar 31 '13 at 00:25
  • @BrianM.Scott I apologize, I meant m≤n≤2m , once I see those, along with other funky requirements, my knowledge of CFG, despite solving over 20 regular ones, goes out the window; hence why I am here trying to figure out how to solve them(there has to be some neat way of solving it, since the answer for those type of problems seem relatively simple when presented to you) – Gaak Mar 31 '13 at 00:29

2 Answers2

4

The basic idea here is that each time you generate an $a$, you should generate either one or two $b$’s to go with it. You need to do this generating in the middle, between the $a$’s on the left and the $b$’s on the right, so you want productions of the form $X\to aXb$ and $X\to aXbb$. And that’s really all that’s needed, so you can start doing that right from the beginning:

$$\begin{align*} S\to ab\mid abb\mid aSb\mid aSbb \end{align*}$$

(That’s assuming that you don’t want the empty word; if you do, just add one more alternative, $S\to\epsilon$.)

Let $m$ be the number of $a$’s at any stage of generating a word, and let $n$ be the number of $b$’s; initially $m=n=0$. Every time you apply the production $S\to aSb$ or the production $S\to ab$, you increase $m$ and $n$ by $1$. Every time you apply $S\to aSbb$ or $S\to abb$, you increase $m$ by $1$ and $n$ by $2$. Suppose that you apply $S\to ab$ or $S\to aSb$ a total of $k$ times, and the other two a total of $\ell$ times. Then you increase $m$ by $k+\ell$ and $n$ by $k+2\ell$, so you end up with $k+\ell$ $a$’s and $k+2\ell$ $b$’s. Since $k,\ell\ge 0$, we clearly have

$$k+\ell\le k+2\ell\le 2k+2\ell=2(k+\ell)\;,$$

i.e., $m\le n\le 2m$, as desired. It’s also not hard to see that we can get every value of $n$ between $m$ and $2m$: to get $n=m+d$, where $0\le d\le m$, just make sure that $\ell=d$ and $k=m-\ell=m-d$.

Brian M. Scott
  • 616,228
  • M.Scott you made this very easy for me, but I still fear these kind of problems, and will try to solve a couple of others, and I see more problems with such conditions, I will post them here. Thank you for your answer. You sir, are brilliant. – Gaak Mar 31 '13 at 00:41
  • @Gaak: Not brilliant; just very experienced! But thank you for the compliment. I’m glad that the answer helped. – Brian M. Scott Mar 31 '13 at 00:43
0

There is already a nice answer by Brian, still, for me the following alternate grammar is more intuitive (it is always good to have alternative solutions):

\begin{align} S &\to \mathtt{a}\,S\,\mathtt{b}\,B \mid \varepsilon \\ B &\to \mathtt{b} \mid \varepsilon \end{align}

It generates words of form $\mathtt{a}^m(\mathtt{b}B)^m$ and each nonterminal $B$ can switch to $\mathtt{b}$ or just disappear, hence it generates language $\{\mathtt{a}^m\mathtt{b}^n \mid m \leq n \leq 2m\}$.

I hope this helps ;-)

dtldarek
  • 37,381