FIRST Set

Question

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

D->d | ɛ

what is FIRST(S)?

Answer 1

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

Comments

check about epsilon... It can't be in FIRST(S)

---

Thanks..

---

I've a doubt. Suppose FIRST(A) didn't contain {ɛ}. then FIRST(S) wouldn't contain {a} as well. Am I right?

---

yes

Answer 2

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}