First Set

For $x \in V_T$:

$$ first(x) = x $$

For $A \to \alpha X \beta$:

$$ first(\alpha X \beta)\subseteq A $$

First Set for Sequence

For a sequence:

$$ Seq = x_1 x_2 \cdots x_n $$

The first set of the whole sequence follows the following rule:

$$ first(Seq) \supseteq first(x_1) $$

• If $\varepsilon \in first(x_1)$:

$$ first(Seq) \supseteq first(x_2x_3 \cdots x_n) $$

• If $\varepsilon \in x_i, \quad i \in [1,n]$:

$$ first(Seq) \subseteq \varepsilon $$

Note $\varepsilon$ could be included in first set, only if a symbol could deduced to $\varepsilon$ by itself.

Checkout TSU book PDFP86 fore more info.

Epsilon Symbol

There’s actually an iteration algorithm that determines if a symbol $X \in V_N$ could be deducted to $\varepsilon$.

• All $x, x \in V_T$, we set $x$ flag to false
• All $X, X \in V_N$, we set $X$ flag to unknown

Then:

• Remove all productions that has false symbol at RHS. (Any false terminal at RHS will cause this production not able to deducted to $\varepsilon$, so just remove it)
  • If a symbol $X$ not in any LHS, mark false (No production has LHS $X$, means no chance to deduct to $\varepsilon$ anymore)
• If production LHS is $X$, RHS is $\varepsilon$, or all symbol at RHS is $true$, set symbol $X$ to true, remove all productions that LHS is $X$. (This is because we don’t need them to determine $X$ flag anymore)

Checkout TSU PDFP85 for more info.