title: "Deterministic Finite Automaton"

Deterministic Finite Automaton

Definition. A deterministic finite automaton (DFA) is a five-tuple $M = (Q, \Sigma, \delta, q_0, F)$ where $Q$ is a finite set of states, $\Sigma$ is an alphabet, $\delta : Q \times \Sigma \to Q$ is a total transition function, $q_0$ is the start state, and $F \subseteq Q$ is the set of accepting states. $M$ accepts $w$ if reading $w$ from $q_0$ ends in a state of $F$.

The finiteness of $Q$ is the entire restriction: the machine reads its input once, left to right, and remembers nothing but which state it is in. Proving what a DFA recognizes means stating what each state means about the input read so far and proving that meaning survives one transition, by induction on the input length. A DFA always halts, taking exactly $|w|$ steps. Introduced in Lecture 3; the languages DFAs recognize are the regular ones.