Context-free language and regular expressions I have the following context-free language:

S -&gt; ASa | b
A -&gt; aA | a


I don't understand why this is not regular. I first said that it's generated by the regular expression a+ba+. The following is regular however

S -&gt; ASa | b
A -&gt; aA | e


e stands for the empty string. I don't understand their differences.
The subtlety is that in the first case, the number of $a$'s before the unique $b$ must be at least the number of $a$ after, i.e. your language is $\{a^nba^m|n\geq m\}$, so it is not regular. This is because each $A$ produces at least one $a$.

In the second case however, this constraint disappears, and your language becomes indeed $b+a^*ba^+$ which is regular.