MadeEasy Test Series: Theory Of Computation - Grammar

Question

G1: S-→ aSa| bSb|e

G2:S--→ aaS|bbS| e

the shortest length strings which does not belongs to L(g1) but belongs to L(G2) is

Comments

e is epsilon

---

i think its terminal .suneetha plzz next time write full : )

then i think anjali007 is correct

---

It should be aabb and length =4

Answer 1

G1 generates L(G1) = { w e w^r | w Є (a,b) and w^r = reverse of w }

G2 generates L(G2) = {  we | w Є (aa + bb)*  }

-----------------------------------------------------------------------------------------------------

now

1st smallest string generated by L(G2) is e which  belongs to L(G1)

2nd smallest string should be aae or bbe which belongs to L(G2)  and this does not belongs to L(G1).

  Answer = length 3 (aae or bbe)

Comments

i have assumed e as a terminal not epsilon