# 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

1. $$b , baa , baaaa , baaaaaa, .....$$
2. $$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 ?

• Every regular grammar is context free grammar as well. So, this would be at least $CFG$. Now try if you could convert it into right linear or left linear or not. That will prove whether it's regular as well or not. – Mr. Sigma. Dec 2 '18 at 12:23
• Here are some further questions. Is this language inherently ambiguous? Can this language be recognized in linear time? – John L. May 2 '19 at 20:37

## 1 Answer

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