Derivační krok
Definice:
Nechť
G
= (
N
,
T
,
P
,
S
)
je
N
G.
Nechť
u
,
v
Î
(
N
È
T
)
*
a
p
=
x
®
y
Î
P
.
Potom
,
u
x
v
přímo
deriv
uje
u
y
v
za použití
p
v
G
, zapsáno
u
x
v
Þ
u
y
v
[
p
]
nebo zjednodušeně
u
x
v
Þ
u
y
v
.
Myšlenka: Změnění řetězce použitím pravidla
Pravidlo
:
x
®
y
x
u
v
…
…
y
u
v
Pozn.
:
Þ
n
,
Þ
+
,
Þ
* a
L
(
G
)
je definováno stejně jako u
bezkontextových gramatik.
27
/45