Context free grammar for $L$

Question

Find context free grammar for

$$ \left\{ w \in \left\{a,b \right\}^* \mid |w|_a = 2k \text{ and } |w|_b = 2l+1, l \in \mathbb{N_{0}}\right\} $$

Any hint helps!

Answer 1

Here is one way to construct a regular expression for the language of all words with an even number of $a$'s and $b$'s (using similar ideas, you can solve your problem). Let us first consider all words without any $aa$ or $bb$. In this case, the regular expression is simply $$ (abab)^* + (baba)^*. $$ Now we want to allow $aa$, i.e., to undo the mapping $aa \to \epsilon$. We simply need to convert any "empty space" to $(aa)^*$, obtaining the regular expression $$ (aa)^*((aa)^*a(aa)^*b(aa)^*a(aa)^*b(aa)^*)^*(aa)^* + (aa)^*((aa)^*b(aa)^*a(aa)^*b(aa)^*a(aa)^*)^*(aa)^*. $$ (This is certainly not the most economical way...) Undoing the mapping $bb \to \epsilon$ by converting any "empty space" to $(bb)^*$, we obtain the desired regular expression, which is however too verbose to write.