Nondeterminism, Closure Properties, Regular Expressions → Finite Automata

Goals

• Nondeterminism
• Closure under $\circ$ and $\ast$
• Regular expressions $\to$ finite automata

Nondeterminism

• multiple paths possible (0, 1 or many at each step)
• ε-transition is a “free” move without reading input
• Accept input if some path leads to accept

Nondetrministic finite automata

$\delta :Q\ast {\Sigma }_{ϵ}\to P(Q)=\{R|R\subseteq Q\}$

${\Sigma }_{ϵ}=\Sigma \bigcup \{ϵ\}$ P(Q) is a power set