Consider the grammar S → SbS | a and the string abababa. Consider the statements: the string has
(A) two parse trees
(B) two leftmost derivations
(C) two rightmost derivations
Which of the following is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. All of (A), (B) and (C) are true
Explanation
The grammar is ambiguous: abababa has more than one parse tree (in fact Catalan(3) = 5). Each parse tree corresponds to one leftmost and one rightmost derivation, so all three statements hold.More Theory of Computation and Compilers questions
- Match List I with List II. Choose the correct answer from the options given below:List I List II A. Type 0 I. Finite automata B. Type 1 II.…
- Consider the following statements: Statement I: An LALR parser is more powerful than a canonical LR parser. Statement II: An SLR parser is…
- Consider the following statements about context-free languages (CFL): Statement I: CFLs are closed under homomorphism. Statement II: CFLs a…
- Match List – I with List – II. List – I (Propositions) (A) P ∧ (P → Q) (B) ¬(P ∨ Q) → (P ∧ Q) (C) P → Q (D) P ∨ (Q ∧ R) List – II (Disjunct…
- Overfitting is expected when we observe that?
- Mr X designed open source software which must comply with some criteria. Choose the false statement in respect of above. (A) No restriction…