Finite-State Machines & Regular Expressions

DFAs, the languages they recognize, and regular expressions.

The idea

A deterministic finite automaton (DFA) is the simplest machine that decides whether a string belongs to a language.

Fix a finite alphabet of symbols. A language over that alphabet is a set of strings built from its symbols — the strings with an even number of $1$s, for example. To recognize a language is to decide, for any string, whether it belongs.

A DFA consists of a finite set of states, one marked as the start state and some marked accepting, together with a transition rule naming, for each state and each symbol, the state to move to next. The machine begins in the start state, reads the string one symbol at a time, moving as the rule directs, and accepts the string if and only if it finishes in an accepting state. The set of strings it accepts is the language it recognizes.

The current state is the machine's only memory. To design a DFA, decide what the machine must remember about the symbols already read in order to continue correctly; the possible values of that memory are its states.

Ways to work on it

• Walkthrough. Trace a DFA, read off its language, and count accepted strings.
• Practice. Trace a small DFA or interpret a regular expression.
• Hardest. Find the minimum number of states a language requires, then trace a counting DFA.

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