Consider the following grammars : G : S → aSb|bSa|aa 1 G : S → aSb|bSa|SS ∣ λ 2 G : S → aSb|bSa|SS ∣ a 3 G : S → aSb|bSa|SS|SSS|λ 4 Which of the following is correct w.r.t. the above grammars? G G

1. A1 and 3 are equivalent G G
2. B2 and 3 are equivalent G G
3. C2 and 4 are equivalent G G
4. D3 and 4 are equivalent L = {anbn−3 ∣ n > 2}

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. 2 and 4 are equivalent G G

Explanation

G2 generates all strings with equal numbers of a's and b's. G4 adds S → SSS, which G2 can already simulate with SS twice, so G2 and G4 are equivalent. G1 and G3 generate different sets (extra a's).