title: "Lecture 5 - Finite Automata - DFAs and NFAs"
unit: 1
lecture: 5

Lecture 5 - Finite Automata - DFAs and NFAs

(Skeleton for Fall 2026.)

Deterministic Finite Automata

TODO: formal five-tuple definition; state diagrams; the language of a machine; regular languages defined.

Nondeterministic Finite Automata

TODO: nondeterminism as guessing / as tree of computations; epsilon transitions; formal definition.

Equivalence of DFAs and NFAs

TODO: the subset construction, proved carefully (structural induction payoff from Lecture 1); exponential state blowup.