Give a context-free grammar that generate this language

Question

Language :

I would like to know if my approach is right or am i missing anything.

Thanks a lot 🙂

My context-free grammar:

$S \Rightarrow aSb $

$S \Rightarrow aaSb $

$S \Rightarrow aab $

$S \Rightarrow ab $

Answer 1

One of the words in the language generated by your CFG, $aab$, is not in $K$. I'd do the following: $$S\to aSC,aC,\varepsilon$$ $$C\to b,bb$$ Starting from $S$, the $S$ rules can be applied $n$ times where $n$ is any natural number (excluding zero), giving $a^nC^n$. The $C$ rules turn the $C$ symbols into $b$ terminals, the latter of which may eventually be any number $m$ from $n$ (if $C\to b$ is always applied) to $2n$ (if $C\to bb$ is always applied). Thus the description of words in $K$ is satisfied exactly.