# FIRST Set

173 views
S->Aa
A->BD
B->b | ɛ

D->d | ɛ

what is FIRST(S)?

1 vote

FIRST(S)

Let the set be k={}

FIRST(S) = see first what A is deriving

A -> BD

now see what B is deriving

case 1  : B->b

so A->bD

so k ={b}

case 2 : B-> ɛ

so A->D

now see what D is deriving

case 2.1 : D->d

so A->d

so k ={b,d}

case 2.2 : D-> ɛ

so A-> ɛ

putting A-> ɛ in S

so S->a

so k = {b,d,a}

so FIRST(S)  = {b,d,a}

First(S) = {a , b , d}

edited
0
check about epsilon... It can't be in FIRST(S)
0
Thanks..
0
I've a doubt. Suppose FIRST(A) didn't contain {ɛ}. then FIRST(S) wouldn't contain {a} as well. Am I right?
0
yes

## Related questions

1
117 views
why do first sets can have epsilon symbol but follow sets don’t? P.S: I’ve a silly doubt :P
Consider following first order logic $\forall x ( \exists y R( x, y ) )$ is equivalent to 1) $\exists y ( \exists x R( x, y ) )$ 2) $\exists y ( \forall x R( x, y ) )$ 3) $\forall y ( \exists x R( x, y ) )$ 4) $\neg \exists x ( \forall y \neg R(x,y) )$ Note: Not sure in the question was it equivalent to or which of these are implied by