Skip to main content
1 of 3
Rick Decker
  • 14.9k
  • 5
  • 42
  • 54

Consider $G_1$. Strings generated by this grammar could be derived by repeated use of the production $S\rightarrow abS$ followed by one use of $S\rightarrow a$ to eliminate the variable $S$. Consequently, we can generate strings in the language by repeatedly adding $ab$ to the right and ultimately stopping by adding an $a$ to the right: $$ S\Rightarrow ab\color{red}S\Rightarrow ab\color{red}{abS}\Rightarrow abababS\Rightarrow\dotsm (ab)(ab)(ab)\dotsm a $$ so we generate strings of the form $$ \underbrace{ab\ ab\ \dotsc ab}_{\text{$0$ or more}}\ a $$ which corresponds to the regular expression $(ab)^*a$, so $L(G_1)$ is regular. Note that $G_1$ is a regular grammar, since it's a right-linear grammar, namely one for which all the productions are of the form $A\rightarrow xB$ or $A\rightarrow x$ where $A, B$ are variables and $x$ is a string of terminals.


Grammar $G_2$ is only slightly more complicated. We now have four productions

  1. $S\rightarrow S_1ab$
  2. $S_1\rightarrow S_1ab$
  3. $S_1\rightarrow S_2$
  4. $S_2\rightarrow a$

Now a string of terminals can only be generated by production (1) adding $ab$ to the left (since the grammar is left-linear), followed by zero or more productions (2) adding another $ab$ to the left, followed by production (3) and then production (4) adding $a$ to the left. We then can generate strings $$ a\ \underbrace{ab\ ab\ \dotsc ab}_{\text{$0$ or more}}\ ab $$ In a way similar to the above, a regular expression denoting $L(G_2)$ could be $ab(ab)^*a$.


Your $G_3$ is not a regular grammar, since in such a grammar, all productions must either be right-linear or left-linear. In $G_3$ the production $A\rightarrow aB$ is right-linear but the production $B\rightarrow Ba$ is left-linear. A regular grammar cannot, by definition, have both right- and left-linear productions.

By the way, $L(G_3)=\{a^nb^n\mid n\ge 0\}$ which you'll soon learn is not a regular language.

Rick Decker
  • 14.9k
  • 5
  • 42
  • 54