A
Derivation Step
Definition: Let G = (N, T, P, S) be a CFG. Let
u, v Î (N È T)* and p = A ® x Î P. Then, uAv directly derives uxv according to p in G, written as uAv Þ uxv [p] or, simply, uAv Þ uxv.
Note: If uAv Þ uxv in G, we also say that G makes a derivation step from uAv to uxv.
 Gist: A change of a string by a rule.
v
u
Rule: A ® x
x
…
u
v
…
5/50