FIRST and FOLLOW Sets for a Given CFG

Verified Sources

Nov 4, 2026

We compute FIRST and FOLLOW sets for the context-free grammar:
$S \to aBDh,\; B \to cC,\; C \to bC \mid \epsilon,\; D \to EF,\; E \to g \mid \epsilon,\; F \to f \mid \epsilon.$

Key supporting definitions/rules we use: epsilon-handling in FIRST computation and end-marker propagation in FOLLOW computation. A nonterminal can have $\epsilon$ in its FIRST set if it can derive the empty string. For FOLLOW, the start symbol’s FOLLOW includes the end marker $$$.

We’ll compute systematically:

FIRST sets for $S,B,C,D,E,F$
FOLLOW sets for $S,B,C,D,E,F$ and show the intermediate reasoning using the standard grammar rules.

FIRST and FOLLOW Sets (Theory + Examples)

Step 1 — Compute FIRST sets

1
Step 1
From $C \to bC \mid \epsilon$ , we have $\text{FIRST}(C)=\{b,\epsilon\}.$
2
Step 2
Since $B\to cC$ , and $c$ is a terminal, the strings derived from $B$ always begin with $c$ ; thus $\text{FIRST}(B)=\{c\}.$
3
Step 3
From $E\to g\mid \epsilon$ , we get $\text{FIRST}(E)=\{g,\epsilon\}.$
4
Step 4
From $F\to f\mid \epsilon$ , we get $\text{FIRST}(F)=\{f,\epsilon\}.$
5
Step 5
Because $D\to EF$ , we combine: start with $\text{FIRST}(E)\setminus\{\epsilon\}$ , and if $E$ can be $\epsilon$ , also include $\text{FIRST}(F)\setminus\{\epsilon\}$ , and if both can be $\epsilon$ , include $\epsilon$ . Here: $\text{FIRST}(E)\setminus\{\epsilon\} = \{g\}$ , $\text{FIRST}(F)\setminus\{\epsilon\}=\{f\}$ , and both can be $\epsilon$ , so $\epsilon$ is included. Therefore $\text{FIRST}(D)=\{g,f,\epsilon\}.$
6
Step 6
Since $S\to aBDh$ , the first symbol is terminal $a$ , so $\text{FIRST}(S)=\{a\}.$

FIRST sets (final)

epsilon-aware results:

Nonterminal	FIRST set
$S$	$\{a\}$
$B$	$\{c\}$
$C$	$\{b,\epsilon\}$
$D$	$\{g,f,\epsilon\}$
$E$	$\{g,\epsilon\}$
$F$	$\{f,\epsilon\}$

Step 2 — Compute FOLLOW sets

1
Step 1
Because $S$ is the start symbol, we include the end marker: $\$ \in\text{FOLLOW}(S) $. So$ \text{FOLLOW}(S)={$}.$
2
Step 2
In $S\to aBDh$ , after $B$ comes $D$ , so add $\text{FIRST}(D)\setminus\{\epsilon\}$ to $\text{FOLLOW}(B)$ . Since $\text{FIRST}(D)=\{g,f,\epsilon\}$ , add $\{g,f\}.$ Also, because $D$ can derive $\epsilon$ , add $\text{FIRST}(h) = \{h\}$ to $\text{FOLLOW}(B)$ . Thus $\text{FOLLOW}(B)\supseteq \{g,f,h\}.$
3
Step 3
In $S\to aBDh$ , after $D$ comes terminal $h$ , so add $h$ to $\text{FOLLOW}(D)$ . Thus $h\in\text{FOLLOW}(D)$ . So $\text{FOLLOW}(D)\supseteq\{h\}.$
4
Step 4
In $B\to cC$ , $C$ is at the end of the right-hand side, so add $\text{FOLLOW}(B)$ to $\text{FOLLOW}(C)$ . Therefore $\text{FOLLOW}(C)\supseteq\text{FOLLOW}(B)\supseteq\{g,f,h\}.$
5
Step 5
In $C\to bC$ , the second $C$ is at the end, so add $\text{FOLLOW}(C)$ to itself (no new information). The $\epsilon$ production also doesn’t add terminals directly.
6
Step 6
In $D\to EF$ , after $E$ comes $F$ , so add $\text{FIRST}(F)\setminus\{\epsilon\}$ to $\text{FOLLOW}(E)$ . Here $\text{FIRST}(F)\setminus\{\epsilon\} = \{f\}$ , so $f\in\text{FOLLOW}(E)$ . Since $F\Rightarrow^*\epsilon$ , also add $\text{FOLLOW}(D)$ to $\text{FOLLOW}(E)$ . We already have $\text{FOLLOW}(D)\supseteq\{h\}$ , so $\{h\}\subseteq\text{FOLLOW}(E)$ . Hence $\text{FOLLOW}(E)\supseteq\{f,h\}.$
7
Step 7
In $D\to EF$ , $F$ is at the end, so add $\text{FOLLOW}(D)$ to $\text{FOLLOW}(F)$ . Therefore $\text{FOLLOW}(F)\supseteq\{h\}.$
8
Step 8
Now that $\text{FOLLOW}(B)=\{g,f,h\}$ , it forces $\text{FOLLOW}(C)=\{g,f,h\}$ . Those values already propagate consistently into $\text{FOLLOW}(E)$ and $\text{FOLLOW}(F)$ via $\text{FOLLOW}(D)=\{h\}$ . No additional terminals appear.

FOLLOW sets (final)

End marker propagation and epsilon-aware propagation yield:

Nonterminal	FOLLOW set
$S$	$\{\\$ \}$
$B$	$\{g,f,h\}$
$C$	$\{g,f,h\}$
$D$	$\{h\}$
$E$	$\{f,h\}$
$F$	$\{h\}$

Pro Tip: Epsilon changes what follows

When you process $X\to \alpha Y\beta$ and $\epsilon\in\text{FIRST}(\beta)$ , you must also add $\text{FOLLOW}(X)$ into $\text{FOLLOW}(Y)$ . This is exactly why $h$ enters $\text{FOLLOW}(B)$ and $\text{FOLLOW}(E)$ .

Pro Tip to avoid a common mistake

Do not add $\epsilon$ itself into FOLLOW sets. FOLLOW contains terminals (and $\$$ for start), not$ \epsilon $. In our computation, we always used$ \text{FIRST}(\cdot)\setminus{\epsilon}$ when adding to FOLLOW.

What you should do (recap roadmap)

Compute FIRST

Phase A

Start from productions with terminals and $\epsilon$ , then build outward (e.g., $C$ , $E$ , $F$ first)."

Compute FOLLOW

Phase B

Initialize FOLLOW( $S$ ) with $$$, then scan each production right-to-left with FIRST(remaining) logic."

Close under propagation

Phase C

Repeat until sets stop growing; epsilon-driven dependencies should already be satisfied."

Knowledge Check

Question 1 of 4

Q1Single choice

In the grammar $S\to aBDh$ , which terminals are added to FOLLOW(B) from FIRST(D) when forming FOLLOW(B)?

{g,f} only

{g,f,h} (because D can be $\epsilon$ )

{h} only

{a} only

Explore Related Topics

DFA Design: Strings over $\{a,b\}$ with at least three occurrences of the substring $bbb$ (overlap allowed)

Constructing an NPDA for a Given CFG

Consider the following grammar: $S \to CC$ $C \to cC | d$ Find the LR(1) set of items.

Browse all research articles