Trying to find two CFGs for the following languages

Question

I'm trying to get CFGs for these two languages which still remain unsolved in my practice problems sheet:

$L = \{ a^kb^ra^m | m=k+r\}$

$L = \{ a^nb^m | 1\leq n\leq 2m\}$

With the first one, I thought of this:

$$S\rightarrow aSa | T$$ $$T\rightarrow b T a | \epsilon$$

but what if $k>r$ or $r>k$?

With the second one, I think it is really simple but I cannot wrap my mind with $1\leq n\leq 2m$ (maybe I'm special...), should I have at least as many $a's$ as the double of $b's$ but not strictly? how could I specify that?

Answer 1

You can write the first language as $$ \{ a^k b^r a^r a^k \mid k,r \geq 0 \}. $$ The corresponding context-free grammar is exactly the one you give. If you apply $k$ times the rule $S \to aSa$ and $r$ times the rule $T \to bTa$, then you will get $a^k b^r a^r a^k$.

As for the second language, let us start with the slightly easier $$ \{ a^n b^m \mid n \le 2m \}. $$ For each $b$ that you add, you can add up to two $a$'s. This leads to the grammar $$ S \to Sb \mid aSb \mid aaSb \mid \epsilon. $$ In your case, you have to guarantee at least one $a$. Write this as follows: $$ \{ a^{n+1}b^{m+1} \mid 0 \leq n \leq 2m+1 \} = \{ a^{n+1}b^{m+1} \mid 0 \leq n \leq 2m \} \cup \{ a^{n+2}b^{m+1} \mid 0 \leq n \leq 2m \}. $$ Thus you can add the following rules to the preceding grammar, making $T$ the new starting symbol: $$ T \to aSb \mid aaSb. $$