GATE CSE 1987 | Question: 1-xii

Question

A context-free grammar is ambiguous if:

• A. The grammar contains useless non-terminals.
• B. It produces more than one parse tree for some sentence.
• C. Some production has two non terminals side by side on the right-hand side.
• D. None of the above.

Comments

If a string has LMD and RMD it has 2 parse trees, right?

---

If a grammar has x number of parse tree then it has x number of LMD and x number of RMD(for every parse tree there is a respective LMD and RMD associated with it.

Answer 1

An ambiguous grammar produces more than one parse tree for any string.

Correct Answer : B.

Comments

But either leftmost derivative or right most derivative is not mentioned?????

---

more than one parse tree means is ambiguous no need to mention it @ana

---

@kirti singh :

An ambiguous grammar produces more than one parse tree for any string.. that's B..

A grammar is ambiguous if there exists atleast one string for which there can be more than one tree.

A grammar is unambiguous if for all strings exactly one tree.(LMD or RMD)

---

A context free grammar is ambiguous if

1. It has more than one RMD

2.It has more than one LMD

3. It has more than one parse tree

---

@Doodle

Please give some example of it..

---

Any grammar is ambiguous if
1. It has more than one RMD

2.It has more than one LMD

3. It has more than one parse tree
not just CFG right?

---

A grammar is ambiguous if, for any string

1) it has more than one parse tree, or

2) there is more than one right-most derivation, or

3) there is more than one left-most derivation (the three conditions are equivalent)

Answer 2

The correct option is B it produces more than one parse tree for some sentence
A context-free grammar is ambiguous if
1. It produces more than one parse tree for some sentence
or
2.It produces more that one leftmost derivation for some sentence
or
3. It produces more than one rightmost derivation for some sentence.

Answer 3

Option B is correct.