) Let G = (V, S, R, S), where V = {a, b, S}, S = {a, b}, R = { S -> aSb, S -> aS
ID: 3934993 • Letter: #
Question
) 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.
Explanation / Answer
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).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.