SKEDSOFT

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

Solution

(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 nbm : n ³ 2, m ³ 3}.

Solution: Right-Linear Grammar: