UGC NET Computer Science December 2019 | Question 93

Question 93

---

Consider the following grammars :
G1:S → aSb|bSa|aa
G2:S → aSb|bSa|SS|λ
G3:S → aSb|bSa|SS|a
G4:S → aSb|bSa|SS|SSS|λ
Which of the following is correct w.r.t. the above grammars?

1. (1) G1 and G2 are equivalent
2. (2) G2 and G3 are equivalent
3. (3) G2 and G4 are equivalent
4. (4) G3 and G4 are equivalent

Answer : (3) G2 and G4 are equivalent

Explanation

We can differentiate the given grammers by count of a's and b's in strings generated by grammer. Lets evaluate each expression to basic level:

G1:
S → aSb → abSab → abaaab
So, Given grammer generates strings where count of a's = ((count of b's) + 2 )
It generates strings like aa, aaab, baaa, abaaab, aaaabb, bbaaaa,..........

G2:
S → aSb → abSab → abSSab → abλλab (abab)
So, Given grammer generates strings where number of a's is equel to number of b's It generates strings like λ, ab, ba, aabb, bbaa, abab, baba, aaabbb.......

G3:
S → aSb → abSab → abSSab → abaaab
So, Given grammer generates strings where number of a's is greater than number of b's. As we can only replace S by a in last production while deriving a string from given production rules of grammer.It can also generate strings which only contains "a" that is a⁺ strings like a, aa, aaa, aaa, .......
It generates all strings like aa, aaa, baa, aab, aaaa, aaab, baaa, aaaaa, abaaaab, baaaaba, aabbaa.......

G4:
S → aSb → abSab → abSSab → abλλab (abab)
So, Given grammer generates strings where number of a's is equel to number of b's It generates strings like λ, ab, ba, aabb, bbaa, abab, baba, aaabbb.......

So, from above we list property of all 4 grammers then:
Grammar G1 generates strings where count of a's = ((count of b's) + 2 )
Grammar G2 generates strings where number of a's is equel to number of b's
Grammar G3 generates strings where number of a's is greater than number of b's
Grammar G4 generates strings where number of a's is equel to number of b's

Lets cosider the equivalence between these grammers:
G1 and G2 are not equivalent
G1 and G3 are not equivalent
G1 and G4 are not equivalent
G2 and G3 are not equivalent
G3 and G4 are not equivalent

G2 and G4 are equivalent

From above list we can conclude that only Grammer G2 and G4 can produces strings where number of a's is equel to number of b's.

So, option 3 is correct answer

Previous	Next
UGC NET CS December 2019 - Question 92	UGC NET CS December 2019 - Question 94