Derivation Step
Definition: Let G = (N, T, P, S) be an URG. Let
u, v Î (N È T)* and p: x ® y Î P. Then, uxv directly derives uyv according to p in G, written as uxv Þ uyv [p] or, simply, uxv Þ uyv.
 Gist: A change of a string by a rule.
Rule: x ® y
x
u
v
…
…
y
u
v
Note: Þn, Þ+, Þ* and L(G) are defined by analogy with the corresponding definitions in terms of CFGs.
27/45