[Solved]: Context-free language and regular expressions

Problem Detail: 

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.

Asked By : Daniel

Answered By : Denis

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21629