# Finite Automaton - NFA and DFA - Converting [[nfa-to-dfa|NFAs to DFAs]] using subset construction. ## Minimizing DFA Using Hopcroft's DFA minimizing algorithm. 1. Partition states $S$ into $T$, such that - $T_0$ = non-accepting states - $T_1$ = accepting states 2. Repeat - $\forall T_i \in T$, and $\forall c \in \Sigma$; - If $T_i$ takes $c$ to more than one state in $T$; - Split $T_i$ into multiple states; - So that ``` for t in T: for c in Sigma if t --c--> more than one state in T split(t), so that each state has 1 action ``` ## Nondeterministic Automaton - Key difference: may have an $\epsilon$ (epsilon transition), which represents an empty string. - Two interpretations: _crystal ball interpretation_ (oracle) and _many-world interpretation_. ## Limits of FA - Hard to write. - Can't express any arbitrary levels of [[nested]] structures.