Finding FIRST sets in a grammar

Question

Today I am reading how to find First and Follow of a grammar. I saw this grammar:

S → ACB | CbB | Ba

A → da | BC

B → g | ε

C → h | ε

The claim is that

FIRST(S) = FIRST(ABC) U FIRST(CbB) U FIRST(Ba)

= {d, g, h, ε} U {h, b} U {g, a}

= {d, g, h, ε, b, a}

I don't understand how a and b are in this set. Can anyone explain this?

Answer 1

Notice that B and C both are nullable (they can produce ε). This means that from the production

S → CbB

we get that b ∈ FIRST(S), since if we use the production C → ε we can get a production that starts with b.

Similarly, note that

S → Ba

is a production, so we get a ∈ FIRST(S) because we can use the production B → ε to get an a at the front of a string derivable from S.

Hope this helps!