fa

Finite Automaton

• NFA and DFA
• Converting 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 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.