I need to write a context-free grammar for this Language :

$\L = {a^nb^k | 1 =< n <= 2k}

Please help me solve this problem! Thanks.

  • 1
    $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ Nov 5, 2015 at 23:01
  • $\begingroup$ This is covered by cs.stackexchange.com/q/33228/755, especially idioms 2, 5, and 6 of this answer. For example: Write this as $L_1 \cup L_2$ where $L_1 = \{a^n b^k : 1 \le n \le k\}$ and $L_2 = \{a^n b^k : k \le n \le 2k\}$. For $L_2$, write $i=n-k$ and $j=k-i$; then $L_2 = \{a^j a^i a^i b^i b^j : i,j \ge 0 \}$. Now it's easy to find CFG's for both $L_1$ and $L_2$ using the techniques at that question. $\endgroup$
    – D.W.
    Nov 5, 2015 at 23:19

2 Answers 2


You can break up this problem into two parts: starting with the shortest legal string with $n$ a's, you can follow it with zero or more b's and still be legal, so you have a string in your language will be the concatenation of $L$ and $X$, where $L$ generates the smallest legal strings and $X$ generates the extra b's.

The $X$ part is easy to produce: $X\rightarrow bX\mid\epsilon$.

Now for the $L$ part we have two cases: the number of a's is even or odd. If we have $a^{2k}$ then we need at least $k$ b's. That's easy to generate as well: $E\rightarrow aaEb\mid aab$, since we're not allowed to have zero a's. If, $n$ is odd, then we must have $2k+1$ a's and $k+1$ or more b's, which is to say we need to generate $aa^{2k}b^{k+1}=aa^{2k}b^kb$. That gives us two subcases: either $ab$ or $a..b$ with $a^{2k}b^k$ inside. That's also easy: $O\rightarrow ab\mid aEb$. Putting all this together, a grammar for your language is $$\begin{align} S &\rightarrow LX\\ L &\rightarrow E\mid O\\ E &\rightarrow aaEb\mid aab\\ O &\rightarrow aEb\mid ab\\ X &\rightarrow bX \mid \epsilon \end{align}$$ Of course we could simplify this a bit. For a more detailed tutorial on this topic, you could look here.


Here's how I would break it down:

Your language consists of an a followed by some number of bs, or two as followed by at least 4 bs, or...

In other words, you take the previous definition and add abb to the middle, or some number of bs to the end

L := M | L b M := a b b | a M b b

(L here is the "add stuff to the end" part, and M is the "add stuff to the middle" part)

Note that you can write this more simply if you allow repeats and optionals.

Then your language becomes simply:

L := a (L) b b b*

That is, your language consists of an b, followed optionally by another statement in the language, followed by two bs, followed by zero or more bs.

  • $\begingroup$ Right track, but you're interpreting things backwards. For example, starting with two $a$'s, you could follow with 1 or more $b$'s, not 4 or more. $\endgroup$ Nov 5, 2015 at 21:34

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