Finite automata and regular languages

An alphabet is a finite set of symbols, a string is a finite sequence of them, and a language is any set of strings. A deterministic finite automaton (DFA) reads a string one symbol at a time. It has a finite set of states, a start state, a set of accepting states, and a transition function saying, for each state and symbol, which state comes next. It accepts a string if it finishes in an accepting state. A two-state DFA that flips state on each 1 and stays put on each 0 accepts exactly the binary strings with an even number of 1s.

A DFA is a finite memory, and counting its accepted strings is a recurrence. Take strings with no two consecutive 1s: states "last symbol was 0 (or nothing yet)" and "last symbol was 1", with a 1 after a 1 leading to a dead state. The numbers of good strings ending in each state obey \( s_n = s_{n-1} + s_{n-2} \), so there are \( F_{n+2} \) good strings of length \( n \), and the example computes \( F_{12} = 144 \) for length 10. In general, if \( T \) is the matrix whose \( (i, j) \) entry counts the symbols leading from state \( i \) to state \( j \), then the entries of \( T^n \) count strings of length \( n \) between states.

A nondeterministic automaton (NFA) may have several possible next states, or none, and accepts if some sequence of choices ends in an accepting state. NFAs are often much smaller to write, but they recognise nothing new: the subset construction builds a DFA whose states are sets of NFA states, at most \( 2^n \) of them for an NFA with \( n \) states. Regular expressions build languages from single symbols by union \( (a \mid b) \), concatenation \( ab \) and repetition \( a^* \), and Kleene's theorem says they describe exactly the languages that finite automata accept: the regular languages.

Not every language is regular. The pumping lemma says that for a regular language \( L \) there is a length \( p \) such that every string in \( L \) of length at least \( p \) can be split as \( xyz \) with \( |xy| \le p \), \( y \) non-empty, and \( xy^iz \in L \) for every \( i \ge 0 \). The reason is pigeonhole: a DFA with \( p \) states reading \( p \) symbols repeats a state, and the loop between the repeats can be run any number of times. The language \( \{0^n1^n : n \ge 0\} \) fails it: take \( 0^p1^p \); since \( |xy| \le p \), the piece \( y \) lies inside the leading 0s, so pumping it changes the number of 0s but not of 1s. The lemma only goes one way: a language that can be pumped is not thereby shown to be regular. A finite memory cannot count without bound.

Picture it: a DFA is a board game with a counter on circles joined by labelled arrows. Each symbol read moves the counter along the arrow with that label, and the string wins if the counter ends on a double circle.

Think it: to design a DFA, decide what the machine must remember about the prefix read so far, and make one state per possibility; if two prefixes can be followed by the same suffixes with the same outcomes, they can share a state. That idea, made precise by the Myhill-Nerode theorem, also gives the minimum number of states.