Question

Determine FOLLOW(S) for the grammar

S→aSb∣cAd
A→aAc∣bS∣ε
​ Here S,A are variables, S is the start variable and the set of terminals is {a,b,c,d}.
- FOLLOW (S)={b, EOS }
- FOLLOW(S)={b,ε}
​- FOLLOW(S)={b,ε,EOS}
- FOLLOW(S) ={b,d}
- FOLLOW(S)={b,d,EOS}
- FOLLOW(S)={b,c,d}
- FOLLOW(S)={b,c,d,EOS}
- FOLLOW(S)={a,b,c,d}
​

Answer 1

The FOLLOW(S) set for the given grammar is {b, EOS}.

Step-by-step explanation:

FOLLOW(S) is the set of terminals that can appear immediately after the nonterminal S in a valid derivation of the given grammar. To determine FOLLOW(S) for the given grammar, we follow these steps:

1. Start with FOLLOW(S) = {} (empty set).
2. If S is the start symbol, add 'EOS' (end of string) to FOLLOW(S).
3. For each production where S appears on the right-hand side:

• If S is followed by a terminal symbol, add that terminal to FOLLOW(S).
• If S is followed by a nonterminal symbol A, add the FIRST(A) (set of terminals that can start a string derived from A) to FOLLOW(S).
• If S is the last symbol in a production (or the production is of the form S → ε), add FOLLOW(left-hand side of the production) to FOLLOW(S).

Repeat steps 3 and 4 until no further changes are made to FOLLOW(S).

For the given grammar, the correct set of terminals in FOLLOW(S) is {b, EOS}.