After spending time with sets, relations, and languages, you finally arrive at the first genuine computational model of this course: the finite automaton. This is the point where Theory of Computation stops feeling like pure mathematics and starts feeling like the beginning of an actual machine, one that reads input symbol by symbol and decides, at the very end, whether to accept or reject what it has seen.
A finite automaton is deliberately simple. It has no scratch paper, no extra memory beyond a fixed number of states, and no way to go back and re-read something it has already processed. Despite these limitations, finite automata are powerful enough to describe an enormous range of practical patterns, from validating email formats to recognizing keywords inside a compiler. Understanding exactly what this simple machine can and cannot do sets the stage for every more powerful model introduced later in this course.
In this tutorial, you will learn the formal definition of a finite automaton, how deterministic and non-deterministic finite automata differ, how to represent them using transition diagrams and transition tables, and how to design your own finite automata to solve simple pattern recognition problems. Several fully worked examples are included so that the abstract definitions feel concrete rather than purely theoretical.
A finite automaton is an abstract machine consisting of a finite number of states, a starting state, one or more accepting states, and a set of rules describing how the machine moves from one state to another based on the input symbol it reads. The machine processes an input string one symbol at a time, moving between states according to these rules, and once the entire string has been read, the machine either accepts or rejects the string depending on which state it ends up in.
Finite automata come in two main varieties. A deterministic finite automaton, commonly called a DFA, allows exactly one possible move for every combination of current state and input symbol. A non-deterministic finite automaton, commonly called an NFA, relaxes this restriction, allowing zero, one, or multiple possible moves for the same combination, and even allowing moves without consuming any input symbol at all.
A deterministic finite automaton is formally defined as a collection of five components, often written as a 5-tuple in the form (Q, Σ, δ, q0, F).
| Component | Meaning |
|---|---|
| Q | A finite, non-empty set of states that the machine can be in at any point. |
| Σ | A finite alphabet describing every symbol the machine is allowed to read as input. |
| δ | The transition function, which takes the current state and an input symbol and returns exactly one next state. |
| q0 | The start state, a single state from Q where the machine begins processing every input string. |
| F | The set of accepting or final states, a subset of Q; if the machine ends in one of these states after reading the entire string, the string is accepted. |
The transition function δ is the heart of a DFA, and it is precisely because δ always produces a single, well-defined next state that the machine is called deterministic. Given any state and any input symbol, there is never any ambiguity about where the machine goes next.
Suppose the task is to design a DFA over the alphabet Σ = { 0, 1 } that accepts every string containing an even number of 1s, including strings with zero 1s. This is a classic example because it demonstrates how a machine with very little memory, just two states, can track a property of the entire string read so far.
Since the machine only needs to remember whether the number of 1s seen so far is even or odd, two states are enough. Call these states q0 and q1, where q0 represents "even number of 1s seen so far" and q1 represents "odd number of 1s seen so far." The machine starts in q0, since zero is an even number, and q0 is also the only accepting state, since the goal is to accept strings with an even count of 1s.
| State | Input 0 | Input 1 |
|---|---|---|
| q0 (start, accepting) | q0 | q1 |
| q1 | q1 | q0 |
Reading a 0 never changes the count of 1s, so the machine stays in the same state whenever it reads a 0. Reading a 1 flips the parity of the count, so the machine switches states whenever it reads a 1. This small transition table completely defines the machine's behavior for every possible input string over Σ.
Input string: 1 0 1 1 Start: q0 Read 1 → q1 Read 0 → q1 Read 1 → q0 Read 1 → q1 Final state: q1 (not accepting) Result: Rejected, because the string contains 3 ones, which is odd.
Input string: 1 1 0 1 1 Start: q0 Read 1 → q1 Read 1 → q0 Read 0 → q0 Read 1 → q1 Read 1 → q0 Final state: q0 (accepting) Result: Accepted, because the string contains 4 ones, which is even.
Tracing strings symbol by symbol like this is one of the best ways to build intuition for how a DFA works, and it is a technique you should practice on every new automaton you design, since it quickly reveals mistakes in a transition table that might otherwise go unnoticed.
A non-deterministic finite automaton relaxes the strict one-move-per-symbol rule found in a DFA. At any given state, reading a particular symbol might lead to several different possible next states, exactly one possible next state, or no valid move at all. An NFA may also include special transitions, often called epsilon transitions, that allow the machine to move to a new state without reading any input symbol whatsoever.
This might sound like it makes NFAs more powerful than DFAs, since they appear to have more freedom in how they move, but this is actually one of the most important and surprising results in Theory of Computation: NFAs and DFAs are exactly equally powerful, meaning every language that can be recognized by an NFA can also be recognized by some DFA, even though that DFA might require considerably more states. The next chapter of this course covers exactly how to construct that equivalent DFA from a given NFA.
An NFA is also defined using a 5-tuple (Q, Σ, δ, q0, F), with the same meaning for Q, Σ, q0, and F as in a DFA. The only difference lies in the transition function δ, which in an NFA maps a state and an input symbol, or the empty symbol epsilon, to a set of possible next states rather than a single state.
Suppose the task is to design an NFA over the alphabet Σ = { a, b } that accepts every string ending in "ab". This particular language is much easier to describe using an NFA than a DFA, because the machine can simply "guess" when it has reached the final two symbols of the string, without needing to track every possibility explicitly.
| State | Input a | Input b |
|---|---|---|
| q0 (start) | { q0, q1 } | { q0 } |
| q1 | { } | { q2 } |
| q2 (accepting) | { } | { } |
In state q0, reading an "a" gives the machine two choices: it can stay in q0, treating this "a" as just another symbol somewhere in the middle of the string, or it can move to q1, effectively guessing that this particular "a" is the second-to-last symbol of the string. From q1, reading a "b" moves the machine into the accepting state q2, confirming the guess was correct.
Input string: b a a b One possible path: Start: q0 Read b → q0 Read a → q0 (choosing not to guess yet) Read a → q1 (choosing to guess here) Read b → q2 Final state: q2 (accepting) Result: Accepted, since at least one valid path ends in an accepting state.
This last point is critical to understanding NFAs correctly: a string is accepted as long as at least one possible sequence of choices leads to an accepting state, even if many other possible sequences of choices would lead to rejection.
| Aspect | DFA | NFA |
|---|---|---|
| Transitions per Symbol | Exactly one next state for every state and input symbol. | Zero, one, or multiple next states are allowed for the same state and input symbol. |
| Epsilon Transitions | Not allowed; every move must consume an input symbol. | Allowed; the machine can change state without reading any input. |
| Ease of Design | Can require more states and more careful planning for complex patterns. | Often easier to design for patterns involving guessing or optional segments. |
| Simulation Complexity | Simple, since only one path through the machine needs to be tracked. | More complex, since multiple possible paths may need to be tracked simultaneously. |
| Computational Power | Recognizes exactly the class of regular languages. | Also recognizes exactly the class of regular languages, despite the added flexibility. |
That final row is worth emphasizing again, since it surprises many students the first time they encounter it. Despite NFAs appearing more flexible and powerful on the surface, both DFAs and NFAs recognize exactly the same class of languages, known as regular languages. The difference lies entirely in convenience and ease of design, not in raw computational power.
Finite automata are not just an academic warm-up exercise before more complicated models. They directly power several tools that programmers interact with regularly, often without realizing a finite automaton is running quietly underneath.
| Mistake | Correct Understanding |
|---|---|
| Forgetting to define a transition for every state and every input symbol in a DFA. | A complete DFA must specify exactly one transition for every possible combination of state and symbol; missing transitions usually imply an implicit dead or trap state. |
| Assuming an NFA rejects a string if any single path leads to rejection. | An NFA accepts a string as long as at least one possible path through the machine ends in an accepting state, regardless of how many other paths fail. |
| Believing NFAs can recognize languages that DFAs cannot. | NFAs and DFAs are proven to be equally powerful, both recognizing exactly the class of regular languages. |
| Confusing the start state with an accepting state. | A state can be both the start state and an accepting state at the same time, as shown in the even-number-of-1s DFA example, but the two roles are conceptually distinct. |
Finite automata represent the simplest computational model studied in Theory of Computation, yet they are powerful enough to describe an enormous range of practical pattern-matching problems. A DFA processes input deterministically, following exactly one path through the machine, while an NFA allows multiple possible paths, including moves that consume no input at all. Despite this added flexibility, both models are mathematically proven to recognize precisely the same class of languages, known as regular languages.
In this tutorial, you learned the formal definitions of both DFA and NFA, walked through fully traced examples of designing and simulating each type of machine, compared their key differences, and explored where finite automata quietly power real software tools. With this foundation, you are ready to move on to the next chapter, where you will learn the systematic subset construction method used to convert any NFA into an equivalent DFA.