Finite Automata (DFA & NFA)

Tracing DFAs, the languages they recognize, and NFA-to-DFA subset construction.

The idea

A deterministic finite automaton (DFA) is the simplest machine model of computation: it reads its input once, left to right, and remembers nothing but which of finitely many states it is in.

To illustrate, suppose someone reads you a long string of $0$s and $1$s and asks whether it contains an odd number of $1$s. One bit of memory suffices — odd so far, or even so far — flipped on each $1$ and left alone on each $0$.

Formally, a DFA has a finite set of states, a designated start state, a transition function giving the next state for each state and input symbol, and a set of accept states. It takes one transition per symbol and accepts the input exactly when it halts in an accept state.

The machine and its language are different objects. The language $L(M)$ of a machine $M$ is the set of strings $M$ accepts — a set, not a procedure — and many different machines recognize the same set. A language is regular when some DFA recognizes it.

Allowing several transitions on one symbol gives a nondeterministic finite automaton (NFA), which accepts a string when some choice of transitions ends in an accept state. NFAs recognize exactly the regular languages: a DFA can track the set of states the NFA could occupy, and there are only finitely many such sets.

Ways to work on it

• Walkthrough. Trace a DFA, decide acceptance, and name its language.
• Practice. Trace a small DFA and decide whether it accepts a string.
• Hardest. Convert an NFA to a DFA by the subset construction.

Not sure where to start? Take the ten-question placement test.