Consider the following grammars: \(𝐺_1:π‘†β†’π‘Žπ‘†π‘βˆ£π‘π‘†π‘Žβˆ£π‘Žπ‘Ž \\…

2019

Consider the following grammars:

\(𝐺_1:π‘†β†’π‘Žπ‘†π‘βˆ£π‘π‘†π‘Žβˆ£π‘Žπ‘Ž \\ 𝐺_2:π‘†β†’π‘Žπ‘†π‘βˆ£π‘π‘†π‘Žβˆ£π‘†π‘†βˆ£πœ† \\ 𝐺_3:π‘†β†’π‘Žπ‘†π‘βˆ£π‘π‘†π‘Žβˆ£π‘†π‘†βˆ£π‘Ž \\ 𝐺_4:π‘†β†’π‘Žπ‘†π‘βˆ£π‘π‘†π‘Žβˆ£π‘†π‘†βˆ£π‘†π‘†π‘†βˆ£πœ†\)

Which of the following is correct w.r.t. the above grammars?

  1. A.

    \(𝐺_1\) and \(𝐺_3\) are equivalent

  2. B.

    \(𝐺_2\) and \(𝐺_3\) are equivalent

  3. C.

    \(𝐺_2\) and \(𝐺_4\) are equivalent

  4. D.

    \(𝐺_3\) and \(𝐺_4\) are equivalent

Attempted by 117 students.

Show answer & explanation

Correct answer: C

Answer: G2 and G4 generate the same language.

Reasoning: describe the language generated by each grammar.

  • G1: The only base production is "aa" (two a's). Each wrapping production a S b or b S a adds one a and one b, so the difference #a - #b stays equal to 2. Hence L(G1) = { w | #a(w) = #b(w) + 2 } (all strings have an excess of two a's).

  • G2: The grammar has the empty string and the only nonconcatenation productions are a S b and b S a, which add one a and one b. Concatenation (S S) preserves equality. Therefore L(G2) = { w | #a(w) = #b(w) } (all strings with equal numbers of a and b, including the empty string).

  • G3: The base production is "a" (one more a than b). The wrapping productions a S b and b S a preserve the difference #a - #b, and concatenation (S S) adds differences. Thus every derivation yields #a - #b β‰₯ 1. So L(G3) = { w | #a(w) = #b(w) + k for some integer k β‰₯ 1 } (strings with a strictly positive excess of a's).

  • G4: This grammar includes the empty string and productions that either add one a and one b or concatenate multiple S's. The SSS production is redundant because repeated binary concatenation (SS) can create any finite concatenation. Therefore L(G4) = { w | #a(w) = #b(w) } (same balanced-language as G2).

Comparisons and counterexamples:

  • G1 vs G3: Not equivalent. Example witness: the string "a" is in G3 (base production) but not in G1 (G1 only produces even-length strings and always has #a = #b + 2).

  • G2 vs G3: Not equivalent. Example witnesses: "a" is in G3 but not in G2, and the empty string is in G2 but not in G3.

  • G2 vs G4: Equivalent. Both generate exactly the strings with equal numbers of a and b. The SSS production in G4 is redundant because binary concatenation (SS) plus the empty string already allows any finite concatenation of balanced pieces; all other productions preserve balance.

  • G3 vs G4: Not equivalent. Example witnesses: the empty string is in G4 but not in G3; the string "a" is in G3 but not in G4.

Conclusion: The only correct claim is that G2 and G4 are equivalent.

A video solution is available for this question β€” log in and enroll to watch it.

Explore the full course: Mppsc Assistant Professor