Answered! Consider the grammars: G1: S → SaS | aa | a G2: S → SS | ε G3: S → SS | a G4: S → SS | aa G5: S → Sa | a…

Consider the grammars:

G₁: S → SaS | aa | a

Don't use plagiarized sources. Get Your Custom Essay on

GET AN ESSAY WRITTEN FOR YOU FROM AS LOW AS $13/PAGE

Order Essay

G₂: S → SS | ε

G₃: S → SS | a

G₄: S → SS | aa

G₅: S → Sa | a

G₆: S → aSa | aa | a

G₇: S → SAS | ε

Describe the language of each of these grammars. Then, identify from the list below a pair of grammars that define the same language.

a) G₁, G₅

b) G₅, G₇

c) G₆, G₄

d) G₁, G₂

I couldn’t understant. Tried many ways. plz explain what is the answer and how? Thanks!!!!!!!!!!!

Expert Answer

here we are just saying that the particular letter on left hand side of -> can also be written as those letters on right hand side of -> . for example : in 1 . they are saying that S can also be written as Sas or aa or a .

in the question, we need to change the left side alphabet to one of the right side everytime.

G1 and G5 are defining same language as we can convert s to any variable in G1 and G2 and we are getting same results every time. but in other two the variables are different hence not same in every case. in G6 and G4

IN G6 if s is replaced by aSa and then s is replaced by a then wwe cannot derrive this solution in case of G4 hence not same grammar.

hence answer is a)G1,G5

Still stressed from student homework?

Get quality assistance from academic writers!

Order now