68 views
S->abA

A->baB

B->aA|bb

convert this to left linear grammar

+1 vote
$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$
selected
+1 vote
The left linear grammar corresponding to the given grammar is given below

S ---> Abb

A ---> Aaba | abba
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$