The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes



convert this to left linear grammar
asked in Theory of Computation by Active (4.1k points) | 68 views

3 Answers

+1 vote
Best answer
$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$
answered by Loyal (9.2k points)
selected by
+1 vote
The left linear grammar corresponding to the given grammar is given below

S ---> Abb

A ---> Aaba | abba
answered by Loyal (8.2k points)
0 votes
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$
answered by Junior (557 points)

No related questions found

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,094 questions
45,587 answers
49,122 users