Regular grrammar

Question

S->abA

A->baB

B->aA|bb

convert this to left linear grammar

Answer 1

$L = \begin{Bmatrix} abbabb, abbaababb, abbaabaababb,.............. \end{Bmatrix}$

 

$L = \begin{Bmatrix} abba(aba)^*bb \end{Bmatrix}$

 

$Left \ Linear \ Grammer :$

 

$S\rightarrow Abb$

$A\rightarrow Aaba/C$

$C\rightarrow abba$

Answer 2

The left linear grammar corresponding to the given grammar is given below

S ---> Abb

A ---> Aaba | abba

Answer 3

A $Left Linear$ grammar is a grammar which has at most one non-terminal on right side and is left recursive.

Now considering the set of strings generated by the given grammar:

$ \{ abbabb,abbaababb,.....\} $

By carefully observing the pattern , we notice that the strings always begin with $ab$ and end with $babb$. Using this information We can easily arrive at the grammar:

$S \rightarrow Ababb$

$A \rightarrow ab|Abaa$