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.
Context-free Grammar To Generate $L=\{a^nb^k | 1 =< n =< 2k }
formal languages;context free;automata;formal grammars
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.