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.
Last updated