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 Þ* ay; y Î (N È T)*}.
 Gist:
First(x) is the set of all terminals that can begin a sentential form derivable from x.
Illustration:
x =
X1
X2
Xn
…
a
 y
x = X1X2 …Xn Þ* ay
a Î First(x)
4/57