Trying to find two CFGs for the following languages 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&gt;r$ or $r&gt;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?
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.
$$