derivation sequence

Quick Reference

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, wj+1 is obtained from wi by rewriting the leftmost (or rightmost) nonterminal in wi. Such sequences exist for all derivable words.

w1w2 ⇒ … ⇒ wn

for each 1≤in,

Subjects: Computing.

Reference entries