Set
Empty
Definition:
Let
G
= (
N
,
T
,
P
,
S
) be a CFG.
Empty
(
x
) = {
e
} if
x
Þ
*
e
; otherwise,
Empty
(
x
) =
Æ
, where
x
Î
(
N
È
T
)
*
.
Gist:
Empty
(
x
) is the set that include
e
if
x
derives
the
empty string
; otherwise,
Empty
(
x
) is empty
Illustration:
x
=
X
1
X
2
X
n
…
x
=
X
1
X
2
…
X
n
Þ
*
e
Empty
(
x
) = {
e
}
e
e
e
…
e
16/57