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