The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
69 views
S->abA

A->baB

B->aA|bb

convert this to left linear grammar
asked in Theory of Computation by Active (4.1k points) | 69 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.5k 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.3k 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 (599 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

40,819 questions
47,500 answers
145,756 comments
62,259 users