2
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mr. Sigma. Dec 2 '18 at 12:23
  • $\begingroup$ Here are some further questions. Is this language inherently ambiguous? Can this language be recognized in linear time? $\endgroup$ – Apass.Jack May 2 at 20:37
2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.