Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I had to make a context free grammar for the following language: $$ \{a^m b^n \mid 1 \le m \le n \le 2m\} $$

What I thought is: \begin{align*} S &\to aXbb \\ X &\to a|aab|abb|ab|E \end{align*}

Is this correct way of writing a CFG?

share|improve this question
    
Your grammar allows only five words: aabb, aaabbb, aabbb, aabbb, abb. Note that, in addition to missing longer words, you are also missing the short word ab. –  Hurkyl Jun 17 '12 at 13:36

4 Answers 4

up vote 4 down vote accepted

CFG should be $$S\rightarrow aSb|aSbb|ab|abb$$ where $S$ is the start symbol.
So for example if you have to produce the word $a^mb^n$ then as we know $m\leq n\leq 2m$ then you will use $2n-m$ times this production ($S \rightarrow aSb$) and $m-n$ times this production ($S \rightarrow aSbb$). hence you will get $(2n-m)+(m-n) \times a$ and $(2n-m)+2(m-n)\times b$ which is desired.

Again if $m\leq n\leq km$ then CFG would be $$S\rightarrow aSb|aSbb|.....|aS\underbrace{bb....b}_{\text{k times}}|ab|abb|......|a\underbrace{bb....b}_{\text{k times}}$$ and here also logic is same.

share|improve this answer
    
There's a small oversight: the empty string is a word in your grammar. –  Hurkyl Jun 17 '12 at 16:40
    
yes the empty string cannot be there. so that needs to be taken care of. –  Richa Sachdev Jun 17 '12 at 16:44
    
We could modify it to be S -> aAb and A-> aAb, aAbb and empty string –  Richa Sachdev Jun 17 '12 at 17:03
    
@Richia: the underlying idea will work, but don't forget that abb is in your grammar.... –  Hurkyl Jun 17 '12 at 17:06
    
@RichaSachdev if you are talking about this $$S\rightarrow aAb \\ A\rightarrow aAb|aAbb|\epsilon$$ then how will you produce $abb$ which is in the language –  Saurabh Jun 17 '12 at 17:06

It's interesting to see so many different ideas. My own hint is that we can produce words by "creating" as and bs iteratively, and each step we can do one of two things: create one a and one b, or create one a and two bs.

(be aware that each answer so far is leading towards a different presentation of the grammar: you can't combine the hints directly, and should probably only think about one at a time)

share|improve this answer
    
Well, I don't see how this is different. You may render the grammar in different ways, but the idea is the same: with every $a$ you generate one or two $b$s; only you decide on this right away, Ayman delays the substitution $B \to b$ for later, and my solution forces the order in some particular way (the multiplication of $b$s is commutative after all). For me it is exactly the same. +1 for the comment in parentheses -- I can imagine that one could easily miss that. –  dtldarek Jun 17 '12 at 15:01
    
The actual execution of our three answers are different, and I get the vague impression that we went through very different thought processes to arrive at our answer. It looks like you had a very algebraic approach to the problem. When I read Ayman's, I get a vague impression of a general technique of inserting intermediate symbols to allow and constrain further choices in a construction. Neither idea crossed my mind when I looked at the problem. –  Hurkyl Jun 17 '12 at 15:24

It's not correct. Consider the word $a^4b^5$. This word belongs to the language because $m=4$, $n=5$ and $1 \le 4 \le 5 \le 2 \times 4$. However, your grammer cannot produce it, as it can produce three "$a$"s at most.

Here is a hint: Make $S$ produce one $a$, one $b$ and one $B$ recursively. Make $B$ produce one $b$ at most. This ensures that $1 \le m \le n$, and $n \le 2m$.

share|improve this answer
    
I can have this. –  Richa Sachdev Jun 17 '12 at 13:41
    
Whats if I change to S-> S1 S2 and S1-> ab S2-> aXbb and X-> aX|aaXb|aXbb|aXb|E. Will this be too long? –  Richa Sachdev Jun 17 '12 at 13:48
    
Among the words that grammar produces are ababb and abaaaaaaaaaaaaaaaabb. –  Hurkyl Jun 17 '12 at 13:52
    
@RichaSachdev - Still incorrect, I'm afraid. This grammar can generate the word $ababb$. –  Ayman Hourieh Jun 17 '12 at 13:52

Hint: $$a^m b^n = a^{2m-n}a^{n-m}(bb)^{n-m}b^{2m-n}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.