Which of the following is true : G1: S → AS | ε A → axb | ε G2: S → aAbS | ε A…

Concept

A grammar is ambiguous when some string in its language has two or more distinct parse trees (equivalently, two or more distinct leftmost derivations) — even one such string is enough, and infinitely many parse trees for one string still counts as ambiguous.

Two grammars are equivalent only if they generate exactly the same language; a single string produced by one but not the other already disproves equivalence.

Every LR(1) grammar admits a unique deterministic parse for each string, so an ambiguous grammar can never be LR(1).

Application

1. Trace ε through G1: S → ε directly gives one parse tree. S → AS with A → ε then S → ε gives a second, distinct tree. Repeating S → AS any number of times, using A → ε at each step before the final S → ε, gives a further distinct tree for every repetition count — all yielding the same string ε. So G1 already has infinitely many parse trees for ε alone, which makes it ambiguous and confirms that the statement about an infinite number of parse trees for some string of G1 holds.

2. Compare the languages: in G1, A → axb | ε lets A produce the terminal string "axb" (a, x and b are all terminals), so "axb" belongs to L(G1). G2's productions (S → aAbS | ε, A → aAb | ε) only ever combine the terminals a and b, so no string containing x can ever appear in L(G2). The two languages therefore differ, so the two grammars are not equivalent.

3. Check G2 for ambiguity: each application of S → aAbS (or A → aAb) nests one matching a…b pair around whatever comes next, and the only way to stop is A → ε or the final S → ε — there is no way to insert an extra ε-step without changing the resulting string, so every string of G2 has exactly one derivation. G2 is therefore not ambiguous, so the claim that both grammars are ambiguous does not hold — only G1 is. For example, take the string "ab": the only way to produce it is S → aAbS with A → ε (contributing nothing between a and b) and the trailing S → ε (contributing nothing after b) — any other choice for A or the trailing S adds more terminal symbols and yields a longer string, so "ab" has exactly one derivation, not two.

4. Since G1 is ambiguous, and an ambiguous grammar can never be LR(1), G1 cannot be LR(1) — so the claim that G1 is LR(1) while G2 is not fails immediately, regardless of G2's own LR(1) status.

Cross-check

Re-deriving axb in G1 (S → AS → (axb)S, then the trailing S is terminated with S → ε) confirms it belongs to L(G1); and it too has infinitely many parse trees, not just ε — extra A → ε steps can be inserted before or after the A → axb occurrence any number of times without changing the resulting string, exactly like the ε case. This is consistent with G1 being ambiguous purely because of its unrestricted ε-recursion in S → AS, and with G2's strictly nested a…b matching giving every string a unique derivation.

Result: "Both are not equivalent" and "There exists a string in the language of G1 for which G1 has an infinite number of parse trees" are TRUE; "Both are ambiguous" and "G1 is LR(1) while G2 is not LR(1)" are FALSE.