Let G V S R S where V a b S S a b R S aSb S aSa S b

) Let G = (V, S, R, S), where

                                                V = {a, b, S},

                                                S = {a, b},

                                                R = {   S -> aSb,

                                                            S -> aSa,

                                                            S -> bSa,

                                                            S -> bSb,

                                                            S -> E }.

Show that L(G) is regular.

Solution

A Language is said to be a context free language, if there exists a CFG G, such that L=L(G).

here our G is context free grammar, G=(V,S,R,S)

in the grammer we have V={a,b,s}, S={a,b}, R={S->aSb,S->aSa,S->bSa,S->bSb,S->E}.

here G=(V,{a,b},R,S)

S-->aSb|aSa|bSa|bSb|E

S-->aabb

S-->aaba

S-->baba

S-->babb

therefore in relation R we have { aabb, aaba, baba, babb }

we dont have any null value, we can say its a regular expression.

S->aSb S

/ | \\

a S b

/ \\

a b

S-->aSa S

/ | \\

a S b

/ \\

a b

simalarly all if we do, we will get a regular expression.

L=L(G).