Every time you search a document with a pattern, validate an email address or compile a program, a tiny mathematical machine called a finite automaton is quietly doing the work. Finite automata are the simplest model of computation, yet they lead to deep results about what can and cannot be recognised with limited memory. This guide explains them clearly, with step-by-step traces you can follow on paper.
Alphabets, Strings and Languages
Automata theory starts with three definitions:
- An alphabet \( \Sigma \) is a finite set of symbols, for example \( \Sigma = \{0, 1\} \).
- A string is a finite sequence of symbols, such as \( 1011 \). The empty string is written \( \varepsilon \).
- A language is any set of strings over \( \Sigma \), such as "all binary strings ending in 0".
The central question is: given a language, can a simple machine decide whether any string belongs to it?
Deterministic Finite Automata (DFA)
A DFA reads a string one symbol at a time, moving between a finite number of states. Formally it is a 5-tuple
$$ M = (Q, \Sigma, \delta, q_0, F) $$
where \( Q \) is the set of states, \( \Sigma \) the alphabet, \( \delta: Q \times \Sigma \to Q \) the transition function, \( q_0 \) the start state and \( F \subseteq Q \) the set of accepting states. After reading the whole string, the machine accepts if it is in an accepting state.
The crucial limitation is memory: the only thing a DFA "remembers" is which state it is in.
Worked Example 1: An Even Number of 1s
Design a DFA that accepts binary strings containing an even number of 1s, and trace it on \( 1011 \) and \( 1001 \).
Step 1. Choose states. We only need to remember whether we have seen an even or odd number of 1s so far: states \( E \) (even, start and accepting) and \( O \) (odd).
Step 2. Transitions.
| State | on 0 | on 1 |
|---|---|---|
| E (start, accept) | E | O |
| O | O | E |
Reading 0 changes nothing; reading 1 flips parity.
Step 3. Trace \( 1011 \). \( E \xrightarrow{1} O \xrightarrow{0} O \xrightarrow{1} E \xrightarrow{1} O \). It ends in \( O \), so the string is rejected. Check: it has three 1s, which is odd.
Step 4. Trace \( 1001 \). \( E \xrightarrow{1} O \xrightarrow{0} O \xrightarrow{0} O \xrightarrow{1} E \). It ends in \( E \), so it is accepted. Check: two 1s, which is even.
Worked Example 2: Binary Numbers Divisible by 3
Design a DFA accepting binary numbers divisible by 3.
Step 1. Key idea. Reading a new bit \( b \) after a number \( n \) produces \( 2n + b \). We only need the remainder modulo 3, so states are \( r = 0, 1, 2 \), with transition
$$ r \to (2r + b) \bmod 3 $$
State 0 is both the start state and the accepting state.
Step 2. Transition table.
| Remainder | on 0 | on 1 |
|---|---|---|
| 0 (start, accept) | 0 | 1 |
| 1 | 2 | 0 |
| 2 | 1 | 2 |
For example, from 1 on bit 1: \( (2 + 1) \bmod 3 = 0 \); from 2 on bit 0: \( 4 \bmod 3 = 1 \).
Step 3. Trace \( 110 \) (decimal 6). \( 0 \xrightarrow{1} 1 \xrightarrow{1} 0 \xrightarrow{0} 0 \). Accepted, and indeed \( 6 = 3 \times 2 \).
Step 4. Trace \( 1011 \) (decimal 11). \( 0 \xrightarrow{1} 1 \xrightarrow{0} 2 \xrightarrow{1} 2 \xrightarrow{1} 2 \). It ends in state 2, so it is rejected, and the machine even tells us the remainder: \( 11 = 3 \times 3 + 2 \).
This shows how a machine with only three states can check divisibility of numbers of any length.
Nondeterministic Finite Automata (NFA)
An NFA may have several possible next states for the same symbol, or none, and may jump on \( \varepsilon \) without reading anything. It accepts if at least one possible path ends in an accepting state. NFAs are often much easier to design. For example, "strings whose third-last symbol is 1" needs only 4 states as an NFA, which simply guesses when the third-last symbol arrives.
Surprisingly, NFAs are no more powerful than DFAs. Michael Rabin and Dana Scott proved in 1959 that any NFA can be converted to an equivalent DFA by the subset construction: each DFA state represents the set of NFA states the machine could currently be in. The price is size; an NFA with \( n \) states can need up to \( 2^n \) DFA states. Rabin and Scott later received the 1976 Turing Award, partly for this work.
Regular Expressions
A regular expression describes a language using three operations:
- Union: \( a \mid b \) means "\( a \) or \( b \)".
- Concatenation: \( ab \) means "\( a \) followed by \( b \)".
- Kleene star: \( a^* \) means "zero or more copies of \( a \)".
For example, \( (0 \mid 1)^*0 \) describes binary strings ending in 0, and \( 0^*(10^*10^*)^* \) describes strings with an even number of 1s, the same language as Example 1.
Kleene's theorem, from Stephen Kleene's work around 1951 (published 1956), states that a language can be described by a regular expression if and only if some finite automaton recognises it. Such languages are called regular languages. This is why tools like grep, text editors and programming language lexers compile regular expressions into automata behind the scenes.
The Limits: Not Everything Is Regular
Because a DFA has finitely many states, it cannot count without bound. Consider
$$ L = \{ a^n b^n : n \ge 0 \} $$
the strings with some \( a \)'s followed by the same number of \( b \)'s. Intuitively, a machine would need to remember \( n \), which can be arbitrarily large.
The pumping lemma makes this rigorous. If \( L \) is regular, there is a number \( p \) such that every string \( s \in L \) with \( |s| \ge p \) can be split as \( s = xyz \) with \( |xy| \le p \), \( |y| \ge 1 \), and \( xy^kz \in L \) for every \( k \ge 0 \).
Proof sketch for \( a^nb^n \):
- Assume \( L \) is regular with pumping length \( p \).
- Choose \( s = a^p b^p \), which is in \( L \).
- Since \( |xy| \le p \), the part \( y \) consists only of \( a \)'s, say \( y = a^m \) with \( m \ge 1 \).
- Pump with \( k = 2 \): \( xy^2z = a^{p+m}b^p \), which has more \( a \)'s than \( b \)'s, so it is not in \( L \).
- This contradicts the lemma, so \( L \) is not regular.
The same reasoning shows that balanced brackets are not regular, which is why compilers use more powerful context-free grammars for parsing nested code.
Where Finite Automata Appear
- Lexical analysis: compilers split source code into tokens (keywords, numbers, identifiers) using DFAs built from regular expressions.
- Text search: pattern matching in editors and command-line tools.
- Network protocols and digital circuits: traffic lights, vending machines and protocol handlers are state machines.
- Game AI: enemy characters often switch between states such as "patrol", "chase" and "attack".
Did You Know?
- The idea of finite-state machines grew partly out of Warren McCulloch and Walter Pitts' 1943 model of neurons, which Kleene was studying when he invented regular expressions.
- Ken Thompson built regular expression search into the QED text editor in the late 1960s, and his NFA-simulation method is still taught today.
- For every regular language there is a unique smallest DFA (up to renaming states), and it can be found mechanically.
Key Takeaways
- A DFA reads input symbol by symbol and remembers only its current state.
- NFAs can be easier to design but recognise exactly the same languages as DFAs.
- Kleene's theorem: regular expressions and finite automata describe the same class, the regular languages.
- The pumping lemma proves some languages, such as \( a^nb^n \), are not regular.
- Automata power compilers, search tools and many everyday control systems.
If you need step-by-step help designing automata, writing regular expressions or proving languages non-regular, Amathify's subject experts and PhD scholars can help; reach out on WhatsApp or through the Ask a Question form.
Stuck on a problem or assignment?
Our experts and PhD scholars solve maths, physics and chemistry — step by step.