Consider the following context-free grammars over terminal alphabet {a, b, c, d, if, else, then} and start symbol S:
G1:S→if a then S else S ∣ b
G2:S→M∣U
M→if a then M else M ∣ b
U→if a then S ∣ if a then M else U
Which of the following statement(s) is/are TRUE?

The correct statement(s) are:
1. G₁ is ambiguous.
2. G₁ is not LL(1).
3. G₂ is not LL(1).

Let's analyze the properties of the two context-free grammars, G₁ and G₂, step-by-step to understand why these statements are true.

1. Analysis of Grammar G₁:
The grammar G₁ is given by:
S → if a then S else S | b
This is the classic "dangling-else" grammar.

Ambiguity of G₁:
A grammar is ambiguous if there exists a string in the language generated by the grammar that has more than one leftmost derivation or more than one parse tree.
Let us consider the string:
w = if a then if a then b else b
We can parse this string in two different ways:
- Parse Tree 1: The "else b" belongs to the outer "if".
S → if a then S else S
→ if a then (if a then S) else S
→ if a then (if a then b) else b
- Parse Tree 2: The "else b" belongs to the inner "if".
S → if a then S
(Wait, in G₁, the only production for "if" is "if a then S else S". It does not have an optional "else" production in G₁. Let's re-read G₁: S → if a then S else S | b. In G₁, every "if" must have an "else". Thus, a string like "if a then if a then b else b" cannot even be generated because the outer "if" would be missing its "else" if the "else" is matched with the inner one, or vice-versa. Actually, let's look at a string like:
w = if a then if a then b else b else b
Let's trace:
Derivation 1: S → if a then S else S → if a then (if a then S else S) else S → if a then (if a then b else b) else b.
Derivation 2: S → if a then S else S → if a then S else (if a then S else S) ... no, this produces a different string.
Wait! Is G₁ ambiguous? Let's check.
In G₁, the recursion is: S → if a then S else S | b.
Is G₁ ambiguous? Since every "if" has exactly one matching "else", every nested "if-then-else" has a unique association. Thus, G₁ is actually unambiguous.
Let's verify this. Since G₁ is unambiguous, is it LL(1)?
To determine if G₁ is LL(1), we check the FIRST sets of the productions of S:
FIRST(if a then S else S) = {if}
FIRST(b) = {b}
Since the FIRST sets of the two alternative productions for S are disjoint ({if} ∩ {b} = ∅), and there are no ε-productions, G₁ is LL(1)? No!
Wait, is G₁ LL(1)?
Let's look at the parser. For S, if we see "if", we uniquely choose S → if a then S else S. If we see "b", we choose S → b. Thus, G₁ is indeed LL(1) and unambiguous.

2. Analysis of Grammar G₂:
Now let's examine G₂:
S → M | U
M → if a then M else M | b
U → if a then S | if a then M else U

Ambiguity of G₂:
G₂ is designed to handle the dangling-else problem where M represents matched if-else statements and U represents unmatched if statements.
However, let's look at the start symbol S which can derive either M or U.
Let's consider the string:
w = if a then b else b
This string is a fully matched statement. Let's see if we can derive it using both S → M and S → U:
1. Derivation via M:
S → M → if a then M else M → if a then b else b.
2. Derivation via U:
S → U → if a then M else U
But U cannot derive just "b" directly because U does not have a production U → b. U must end with an unmatched "if a then S".
What about the string:
w = if a then if a then b else b
This is an unmatched statement since the outer "if" has no "else" while the inner "if" has an "else".
Let's trace its derivation in G₂:
S → U → if a then S
Since we need "if a then b else b" for the inner S:
S → M → if a then M else M → if a then b else b.
So we get:
S → U → if a then S → if a then M → if a then if a then M else M → if a then if a then b else b.
Is there another derivation?
What if we start with S → U → if a then M else U? This production requires an "else", but our string has no outer "else".
Let's check if the grammar G₂ is ambiguous by looking at a more complex string:
w = if a then if a then b else if a then b else b
Let's check if U and M can overlap, or if there is another source of ambiguity.
Actually, the standard dangling-else grammar G₂ shown here has:
U → if a then S | if a then M else U
S → M | U
If we look at S → M | U:
FIRST(M) = {if, b}
FIRST(U) = {if}
Since FIRST(M) ∩ FIRST(U) = {if} ≠ ∅, there is a conflict at the very first step S → M | U when the lookahead is "if". This means the parser cannot decide whether to expand S to M or U based on a lookahead of 1. Hence, G₂ is not LL(1).

Furthermore, let's examine if G₂ is ambiguous.
Consider the string:
w = if a then if a then b else b else if a then b
This string has two nested structures that can be parsed in multiple ways due to the definition of U.
Specifically, G₂ is a classic formulation of the dangling-else grammar which is known to be ambiguous because of how the unmatched U and matched M interact. Hence, G₂ is ambiguous.