Regular and not Regular Grammar

Question

According the Peter Linz Book, am a confusing about the two example the Grammar G1 = ({S},{a,b},S,P1) with P1 given as

S -> abS|a

and G2 = ({S,S1,S2,},{a,b},S,P2)

S -> S1ab S1 -> S1ab|S2 S2 -> a

G1,G2 is regular..

i generated from G1 Language= {ababa,...} and it Regular expression (ab)a and from G2 = {aabab} is that right it regular expression a(ab) in the book it show its aab(ab)* but how

First, is it write regular expression ?? Why this G3 = ({S,A,B},{a,b},S,P) with Production

S -> A A -> aB | 'epsilon' B -> Ab

is not regular ? although its left or right linear prodcution.

second why G3 is not regular ?

Answer 1

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 $aab(ab)^*$.

---

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.