Does this context-free grammar generate a regular language?

Does the following set of production rules produce a regular language or not?

$S \to AB \mid b $

$A \to SB$

$B \to AS \mid a$

I have generated following words with above grammar

• $b , baa , baaaa , baaaaaa, .....$

• $bbaba , babab , bababaa , bbbabba ,.....$

But I am not able to create a language using it.
Is this grammar just context free or is this regular also ?
If yes, how to prove that ?

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>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$

StackExchange Computer Science Q#100862, answer score: 3