What is a LEFTMOST DERIVATION?
Aa derivation that always picks the rule listed first in $R$
Bat each step, the LEFTMOST non-terminal in the sentential form is expanded
Ca derivation from $\varepsilon$ back to $S$
Da derivation that uses only left-recursive rules
Answer & Solution
Correct answer: B. at each step, the LEFTMOST non-terminal in the sentential form is expanded
1. In a CFG, at each derivation step you choose a NON-TERMINAL in the current sentential form and apply a production rule to it.
2. LEFTMOST DERIVATION: always expand the LEFTMOST non-terminal.
3. RIGHTMOST DERIVATION: always expand the RIGHTMOST non-terminal.
4. Each parse tree corresponds to exactly one leftmost derivation (and one rightmost derivation). So leftmost/rightmost derivations and parse trees are EQUIVALENT representations.
5. Ambiguity is defined via distinct parse trees (or equivalently, distinct leftmost derivations).
6. Options A, C, D mismatch the definition.
_Source: Jeff Erickson, "Models of Computation", §5.6 (Leftmost and rightmost derivations)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?Is the language $L = \{a^n b^n c^n \mid n \geq 0\}$ context-free?