A machine with a few states and nothing else
A finite automaton is about the simplest computing model there is. It has a fixed, finite list of states, a start state, and a rule that says which state to move to when it reads each input symbol. It reads its input one symbol at a time, left to right, never goes back, and has no other memory than its current state. When the input ends, it either accepts or rejects depending on which state it stopped in.
Here is a concrete example. Suppose the input is a string of 0s and 1s, and we want to accept strings containing an even number of 1s. Two states are enough:
- State Even (the start state, and the accepting state): reading 0 stays in Even, reading 1 moves to Odd.
- State Odd: reading 0 stays in Odd, reading 1 moves to Even.
For the input 1101, the machine goes Even, Odd, Even, Even, Odd, and ends in Odd, so it rejects. There are three 1s, which is odd, so that is correct. The machine never counted; it only remembered one bit of information, whether the count so far is even or odd.
What fixed memory can do
Finite automata recognize exactly the languages that can be described by regular expressions, which is why they power much of text searching and tokenizing. Typical tasks include:
- Checking that a string ends in a given suffix.
- Checking that a number has an even number of digits or a certain remainder when divided by a small fixed number.
- Recognizing a fixed set of keywords.
- Following simple protocols with a small number of modes.
All of these need only a bounded amount of memory about what has been seen so far. If the question can be answered by remembering a fixed number of facts, a finite automaton can usually do it.
Where it breaks
Now ask the machine to accept only strings made of some number of 0s followed by the same number of 1s, such as 000111. The machine would have to remember how many 0s it saw. But any particular automaton has a fixed number of states, say k. If it reads more than k zeros, then by the pigeonhole principle it must pass through the same state twice while reading them. After that, it cannot tell the difference between having seen two different counts of zeros, and so it will treat 0 repeated n times followed by n ones, and 0 repeated a different number of times followed by n ones, the same way. One of those must be wrong.
This argument is a simplified form of what is often called the pumping lemma. The takeaway is that no finite automaton can count without a limit. Matching brackets to arbitrary depth fails for the same reason: nesting depth is an unbounded number.
Adding a stack, and then more
Give the machine a stack, a pile it can push to and pop from, and it can match brackets by pushing on each opener and popping on each closer. Such a pushdown automaton recognizes a larger class of languages, including nested structures. It is still not fully general. A single stack can only be accessed from the top, and some tasks, such as matching three equal counts in a row (as many 0s as 1s as 2s), are beyond it.
Allow two stacks, or a tape that can be moved back and forth and rewritten, and you reach full computing power. This is the jump from limited machines to a Turing machine: the memory is unbounded and can be revisited. That is the core difference between a finite automaton and a full programming language.
Why programmers should care
The distinction is about memory, not about how fancy the instructions are. Consider a program in any language that is run with a strict, fixed limit on memory, with no way to grow it. Even if the language has loops, variables and functions, the combined state of the program is one of a finite (if enormous) number of possibilities. In principle such a program is a finite automaton in disguise. The theory is not wrong to say so; it just means that “finite” can mean “far too large to enumerate.”
This matters for the discussion of infinite memory versus real machines, where the same point shows up from the hardware side. It also matters for the question of whether a language like the Befunge language is truly universal when its playfield has fixed dimensions, which hinges on whether anything in the language can grow without limit, such as the stack.
A practical way to classify an odd language
When you meet a new esoteric language, ask what its memory looks like.
- If it has only a fixed number of cells with a bounded range of values, it is a finite automaton in principle.
- If it has one unbounded stack and nothing else, it resembles a pushdown automaton.
- If it has an unbounded tape or two unbounded counters or stacks, it can be universal, as with counter machines.
This quick check does not replace a proof, but it tells you which direction to look. A language can look wild and still sit on the lowest rung, and a language with only a few commands can sit on the top one. The next step up the ladder is usually explained through the Turing machine model, where the tape removes the memory limit.