سوال ۴۸ کنکور ارشد مهندسی کامپیوتر ۱۴۰۴

A grammar is ambiguous if some string has two distinct parse trees (equivalently, two distinct leftmost derivations). We test each candidate string against

$S \to A0 \mid S1 \mid 1, \qquad A \to 1S \mid 1A \mid 0.$

Key structural facts: every string produced via $S \to A0$ ends in $0$; every string via $S \to S1$ or $S \to 1$ ends in $1$. Also $A$ can never derive a single $1$ (its productions are $1S$, $1A$, $0$).

String 1111 (option 1). It ends in $1$, so it cannot use $S \to A0$. The only path is repeated $S \to S1$ down to the base $S \to 1$: $S \Rightarrow S1 \Rightarrow S11 \Rightarrow S111 \Rightarrow 1111$. This is forced and unique — no ambiguity.

String 1101 (option 2). Ends in $1$, so $S \to S1$ with $S \Rightarrow 110$. Since $110$ ends in $0$, it uses $S \to A0$ with $A \Rightarrow 11$. Now $A \Rightarrow 11$ must be $A \to 1S$ with $S \to 1$ (the alternative $A \to 1A$ would need $A \Rightarrow 1$, which is impossible). Every step is forced — unique, no ambiguity.

String 1110 (option 3). Ends in $0$, so it must use $S \to A0$ with $A \Rightarrow 111$. But $A \Rightarrow 111$ has two distinct derivations:

• $A \to 1A \to 1(1S) \to 1\,1\,1$ (using $S \to 1$)
• $A \to 1S \to 1(S1) \to 1\,1\,1$ (using $S \to 1$)

These give two different parse trees for $A \Rightarrow 111$, hence two parse trees for $S \Rightarrow 1110$. So the grammar is ambiguous on 1110.

Option 4 is therefore false: the grammar is ambiguous.

The correct choice is option 3.

Exam trick: To spot ambiguity fast, anchor on the last symbol. A trailing $0$ forces $S \to A0$, pushing all the work into $A$, and $A$'s two right-recursive rules $1A$ and $1S$ (the latter feeding $S$'s own right recursion $S1$) are exactly what create two ways to lay down the same run of $1$s.