Set
First
Definition:
Let
G
= (
N
,
T
,
P
,
S
) be a CFG. For
every
x
Î
(
N
È
T
)
*
,we define the set
First
(
x
) as
First
(
x
) = {
a
:
a
Î
T
,
x
Þ
*
a
y
;
y
Î
(
N
È
T
)
*
}.
Gist:
First
(
x
) is the set of all terminals that can
begin a sentential form derivable from
x
.
Illustration:
x
=
X
1
X
2
X
n
…
a
y
x
=
X
1
X
2
…
X
n
Þ
*
a
y
a
Î
First
(
x
)
4/57