World's most popular travel blog for travel bloggers.

[Answers] Context-free Grammar To Generate $L=\{a^nb^k | 1 =< n =< 2k }

, , No Comments
Problem Detail: 

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.

Asked By : Masih R.

Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49120

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback