GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 4

Question

A context-free grammar $G$ is ambiguous if and only if

• A. some string $w \in L(G)$ has different leftmost and rightmost derivations.
• B. some string $w \in L(G)$ has at least two different parse trees.
• C. every string $w \in L(G)$ has at least two different parse trees.
• D. some string $w \in L(G)$ has at least two different leftmost derivations.

Answer 1

A context-free grammar is ambiguous if it has multiple leftmost derivations or parse trees for some input string.

Reference: https://en.wikipedia.org/wiki/Ambiguous_grammar

Comments

Why option c is not correct???

---

There is “only if” in the statement.

Answer 2

A CFG is ambiguous if one or more terminal strings have multiple leftmost derivations from the start symbol.  Equivalently: multiple rightmost derivations, or multiple parse trees.

Reference:http://infolab.stanford.edu/~ullman/ialc/slides/slides7.pdf

So, the correct answer is $B;D.$

Comments

in question if and only if is there then also D is right ? suppose a string has 2 rightmost derivation then also it is ambiguous then how D is valid ?

---

Can you give a counter example for D?

---

Because two  rightmost  derivation implies two leftmost derivation, therefore  “A grammar is ambiguous implies it has two leftmost derivation” is again true.

Few more points

A sentence which has more than one leftmost derivation for a given grammar will also have more than one rightmost derivation and vice versa.

Ambiguous grammar is defined as, "An ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree."