2024-09-11

RECAP

Kleene's Theorem : revisited

---

Construction of String Recognisers

Thompson's construction

• NFA will have exactly 1 start, 1 accepting state.

• Inductively $R_1|R_2$ and $R_1 * R_2$ , and $R^*$are defined.

Subset construction

If there's another state reachable without consuming a symbol(that is, connected by $\epsilon$),we can merge the states and denote possible states in subset notation.

$\epsilon$-Closure (of $I$)

The set of states reachable from $I$ without consuming any symbols.

• itself is contained.

• For multiple states in $I$, it is induced by computing the union of each state's $\epsilon$-closure.