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 ?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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