# Conversion Of Left-linear Grammar Into Right-linear Grammar

1 min read

**Example 1: **Give some example of context-free languages.

S**olution**

(a) The grammar *G *= ({*S*}, {*a*, *b*}, *S*, *P*) with productions

*S *-> *aSa*, *S *-> *bSb*, *S *-> l

is context free.

*S *Þ*aSa *Þ*aaSaa *Þ*aabSbaa *Þ*aabbaa*

Thus we have *L*(*a*) = {*ww** ^{R}*:

*w*Î{

*a*,

*b*}*}.

This language is context free.

(b) The grammar *G*, with production rules given by

is context free. The language is

*L*(*G*) = {*ab *(*bbaa*) *n **bba*(*ba*) *n *:*n *³ 0}

**Example 2**: Construct right-and left-linear grammars for the language *L *= {*a **n**b**m *: *n *³ 2, *m *³ 3}.

S**olution**: Right-Linear Grammar: