Reduction of the Number of Derivations
Theorem
:
Let
G
= (
N
,
T
,
P
,
S
) be a CFG.
The next three languages coincide
(1) {
w
:
w
Î
T
*
,
S
Þ
lm
*
w
}
(2) {
w
:
w
Î
T
*
,
S
Þ
rm
*
w
}
(3) {
w
:
w
Î
T
*
,
S
Þ
*
w
} =
L
(
G
)
Gist:
Without any loss of generality, we can
consider only leftmost or rightmost
derivations
.
17/50