Does this context-free grammar generate a regular language?
The grammar can be transformed to

$\quad$ $S \to SBB \mid b $
$\quad$ $B \to SBS \mid a$

Let $L_S$ be the language generated by the rules above (with $S$ as the start symbol). $L_S$ is context-free by definition. 

We will prove it is not regular. The idea comes from the rule, $B\to SBS$.



Let $L_B$ be the language generated by the two rules above with $B$ as the start symbol.

Claim: We have the following inclusions of languages.
$\quad\{b\}\cup\{b^{i+1}ab^ia\mid i\ge0\}\subseteq L_S$
$\quad\{b^iab^i\mid i\ge0\}\subseteq L_B$ 

Proof: Use mathematical induction on $n$, the upper bound for $i$. 


The base case when $n=0$. $S\Rightarrow SBB \Rightarrow^*  baa$ and $B\Rightarrow a$. 
Suppose it is true for $n$. Then $B\Rightarrow SBS\Rightarrow^* b(b^nab^n)b=b^{n+1}ab^{n+1}$. $S\Rightarrow SBB\Rightarrow^* b(b^{n+1}ab^{n+1})a=b^{(n+1)+1}ab^{n+1}a$. So it is true for $n+1$ as well.




Claim: We have following inclusions of languages.
$\quad L_S\subseteq E_S :=\{ba^{2i}\mid i\ge0\}\cup\{b^{i+1}ab^ia\mid i&gt;0\}\cup\{\text{words that have at least three } a\text{'s}\}$
$\quad L_B\subseteq E_B:=\{a\}\cup\{\text{words that have at least two } a\text{'s}\}$  

Proof: It is easy to check that $E_SE_BE_B\subseteq E_S$, $a\in E_S$, $E_BE_SE_B\subseteq E_B$ and $b\in E_B$.



The above two claims implies that $L_S\cap L(b^*ab^*a) = \{b^{i+1}ab^ia\mid i\ge0\}$, which is not a regular language. Since $L(b^*ab^*a)$ is regular, $L_S$ cannot be regular.



Exercise 1. Show that the following grammar generates a regular language.
$\quad$ $S \to SAS \mid b $
$\quad$ $A \to ASA \mid a$



Exercise 2. Show that the following grammar generates a non-regular language.
$\quad$ $S \to AB \mid b $
$\quad$ $B \to SA $
$\quad$ $A \to BS \mid a$