Which of the following statements is/are TRUE? (i) The grammar S → SS / a is…
2017
Which of the following statements is/are TRUE?
(i) The grammar S → SS / a is ambiguous (where S is the start symbol).
(ii) The grammar S → 0S1 / 01S / ε is ambiguous (the special symbol ε represents the empty string and S is the start symbol).
(iii) The grammar (where S is the start symbol)
S → T / U
T → xSy / xy / ε
U → yT
generates a language consisting of the string yxxyy.
- A.
Only (i) and (ii) are TRUE
- B.
Only (i) and (iii) are TRUE
- C.
Only (ii) and (iii) are TRUE
- D.
All of (i), (ii) and (iii) are TRUE
Attempted by 41 students.
Show answer & explanation
Correct answer: D
To determine ambiguity, check if any string has multiple parse trees. For grammar (i), S → SS | a, the string 'aaa' can be derived as S ⇒ SS ⇒ (SS)S or S ⇒ SS ⇒ S(SS), creating different parse trees. Thus, statement (i) is true.
For grammar (ii), S → 0S1 | 01S | ε, the string '01' has derivations S ⇒ 0S1 ⇒ 01 and S ⇒ 01S ⇒ 01. Since two distinct leftmost derivations exist, the grammar is ambiguous, making statement (ii) true.
For grammar (iii), the recursive rules involving T and U allow generating specific strings. Analyzing the production S → T | U confirms that xyxy is in the generated language, validating statement (iii).
A video solution is available for this question — log in and enroll to watch it.