Context-free language and regular expressions

I have the following context-free language:

S -> ASa | b
A -> 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 -> ASa | b
A -> aA | e


e stands for the empty string. I don't understand their differences.

2 Answers

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.

See, in the CFG grammar you need to store the value of n and m in order to compare the condition i.e. n>= m.So memory is required,preferably a stack.Whereas, in the regular grammar its either b or any string ending with ba. You don't need anything to remember to satisfy the grammar,as there is no such condition where you need to store the value.

• I am not the original down-voter but your answer is very vague and, in parts, incorrect. What does it mean to say "in the CFG Grammar, you need to store the value of $n$ and $m$"? $n$ and $m$ are not mentioned anywhere in the question. And a grammar is just a set of rules for producing strings: you don't need to store any integers to do that. Why is a stack the preferred way to remember integers? The regular grammar does not generate $b$ or any string ending $ba$: for example, it includes $abaa$ but not $bba$. – David Richerby Feb 14 '14 at 12:49