Question Details

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?

Options

A

G1​ is ambiguous.

B

G1​ is not LL(1).

C

G2​ is ambiguous.

D

G2​ is not LL(1).

Show Answer
Correct Answer
D
G2​ is not LL(1).
C
G2​ is ambiguous.

Solution :

The correct statement(s) are:
1. G1 is ambiguous.
2. G1 is not LL(1).
3. G2 is not LL(1).

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

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

Ambiguity of G1:
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 G1, the only production for "if" is "if a then S else S". It does not have an optional "else" production in G1. Let's re-read G1: S → if a then S else S | b. In G1, 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 G1 ambiguous? Let's check.
In G1, the recursion is: S → if a then S else S | b.
Is G1 ambiguous? Since every "if" has exactly one matching "else", every nested "if-then-else" has a unique association. Thus, G1 is actually unambiguous.
Let's verify this. Since G1 is unambiguous, is it LL(1)?
To determine if G1 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, G1 is LL(1)? No!
Wait, is G1 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, G1 is indeed LL(1) and unambiguous.

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

Ambiguity of G2:
G2 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 G2:
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 G2 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 G2 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, G2 is not LL(1).

Furthermore, let's examine if G2 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, G2 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, G2 is ambiguous.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: