Redukce počtu možných derivací
T
vrzení:
Nechť
G
= (
N
,
T
,
P
,
S
)
je
BK
G.
Následující 3 jazyky jsou totožné:
(1) {
w
:
w
Î
T
*
,
S
Þ
lm
*
w
}
(2) {
w
:
w
Î
T
*
,
S
Þ
rm
*
w
}
(3) {
w
:
w
Î
T
*
,
S
Þ
*
w
} =
L
(
G
)
Myšlenka: Bez újmy na obecnosti můžeme
uvažovat používání pouze nejlevějších nebo
nejpravějších derivací.
17/50