derivation sequence

views updated

derivation sequence In formal language theory, a sequence of words of the form w1w2 ⇒ … ⇒ wn

(for notation see semi-Thue system). For a context-free grammar, such a sequence is leftmost (or rightmost) if, for each 1←in,

wi+1 is obtained from wi by rewriting the leftmost (or rightmost) nonterminal in wi. Such sequences exist for all derivable words.