derivation (505B)
1 # Derivation 2 3 A *derivation* for a [CFG] G is a sequence of [protowords] starting at the [axiom] and where at every step some [nonterminal] is replaced by the [RHS] of a [production] for that [nonterminal]. If the derivation ends in a [word] w without [nonterminals], then it witnesses that w is in the [language_accepted_by] G 4 5 Notion of [left_derivation], which is in bijection with [derivation_trees] 6 7 - [derivation_index] 8 9 Up: [context_free_grammar] 10 11 See also: [derivation_tree] 12 13 Aliases: derivations