On State Machines
When we talk about state machines in the general sense, let us first look at the finite state machine, or FSM for short.
In the theory of computation, the FSM is the foundation of everything—and the least powerful machine. Above it lies the context-free language (CFL), and above that the Turing machine.
An FSM solves the question: given an input sequence, what state does it end up in after passing through the FSM? For whether a string ends with \0 (C’s string representation), an FSM can answer.
CFLs are the foundation of all programming languages. Whether a piece of Python code you wrote is syntactically correct—a CFL can answer.
The Turing machine is the foundation of the algorithms we use daily to solve problems in code. Loosely speaking, the JVM is a Turing machine.
Beyond that lies the unknown—problems even a Turing machine cannot solve.
If you’ve worked for many years and have already returned your FSM knowledge to your teacher, no worries—let me give you a quick refresher.
An FSM first has a set of states. Depending on the input, it transitions from one state to another. Among these states, some are special—accept states. If, when the input is exhausted, the FSM is in an accept state, then processing succeeds; otherwise it fails.
That’s it. So simple it hardly looks like a heavyweight.
Let’s look at an example. Here’s the question: write a state machine that verifies a string of binary bits contains an even number of 0s and an odd number of 1s.
Valid inputs include: 1, 100, 10101
Invalid inputs include: 10, 00, 1100
We know that when writing a program, once you get the data structure right, you’ve solved 80% of it. Developing an FSM is the same: choosing the right states is the most critical part. Once the states are fixed, what remains is just grunt work.
For this simple problem, everyone can see at a glance that there may be four states. A binary string contains:
- An even number of 0s and an even number of 1s (EE)
- An even number of 0s and an odd number of 1s (EO)
- An odd number of 0s and an even number of 1s (OE)
- An odd number of 0s and an odd number of 1s (OO)
The initial state of the FSM is EE: no bit has been processed, so the counts of both 0s and 1s are even. The accept state is EO. If it ends in this state, processing succeeds.
It is easy to draw such a state machine:
One stroke and it’s done—success achieved. It’s so simple it almost insults your intelligence.
Let’s try a hard one—the kind that might leave you scratching your head and shouting at the top of your lungs without finding an elegant solution.
Here’s the question: determine whether a binary string is divisible by 3.
Valid inputs include: 11, 110, 1001, 1100, 1111, …
There are a great many invalid inputs, and just looking at the inputs seems to reveal no pattern. So you cannot describe it with just two states (divisible / not divisible).
Note that an FSM is dumb: it can only process input one unit at a time (here, one bit per unit). You cannot, while eating what’s in your bowl, look into the pot (peek ahead at future input), nor can you spit out what’s in your stomach and chew it again (backtrack over processed input). All you can rely on is the current state and the current input.
Talk is cheap; let’s throw some input at it and see.
If the first input is 1, then it is not divisible by 3. The quotient is 0 and the remainder is 1. Whether a number is divisible depends on whether the remainder is 0. Besides 0, the possible remainders here are 1 and 2. Let’s try setting the states to 0, 1, and 2 and see if this yields a solution. Here 0 is both the accept state and the initial state. OK: starting from state 0, the input is 1, so the state transitions to 1.
If the second input is 0, that is, the string seen so far is 10, what is the relationship between 10 and 1? Carry! In binary, every two carries one, so it is equivalent to multiplying the dividend by 2. Multiplying the dividend by 2 is equivalent to multiplying the remainder by 2 and then taking it modulo the divisor (I won’t prove this here).
So when the second input is 0, the remainder is (1 * 2) % 3 = 2, and the state transitions from 1 to 2.
If the second input is 1, then multiply by 2, add 1, and take the modulus; the remainder is (1 * 2 + 1) % 3 = 0, and the state transitions from 1 to 0.
Following this line of thought, we can draw the following FSM:
Have you ever thought that the answer you racked your brain for could turn out so neat, so elegantly beautiful, that it takes your breath away? It’s like the first time I saw ‘Dream of the Red Chamber’ paired with ‘Aoi Sora’—a match for the ages—I nearly dropped half a bowl of drool in shock.
In the process of constructing an FSM, no matter how many computations you did or how much brainpower you expended, what you ultimately get is a dictionary: in state x, given input a, go to state y. This is why the FSM is often the most efficient algorithm: you have already compiled the hardest part into the FSM; what remains is table lookup.
All right, you’ve been working so conscientiously, let’s do one more: determine whether a binary string is divisible by 8.
What’s so hard about that! Division by 8 has 8 possible remainders, so eight states. Then copy the same pattern, bla bla bla, and it’s done.
Right? Right. Complicated? Quite. If you had to determine divisibility by 16 this way, a single sheet of A4 paper probably wouldn’t be enough to draw all the state transitions.
Is there another way? Certainly.
Valid inputs include: 1000, 10000, 11000, 111000, 101000, …
The pattern is obvious: they end in 000. That is indeed the definition of a multiple of 8. This FSM is easy to write:
It is also much simpler and clearer than the FSM produced by the previous algorithm.
Note: there is a small issue here—0 is not accepted by the above state machine, but it is divisible by 8. A more rigorous and correct version looks like this (we won’t fuss over such details below):
Clearly, the same problem can be handled by different FSMs. Some are complex, some simple. We should strive for the FSMs with the fewest states.
All the FSMs described above are DFAs (Deterministic Finite Automata). That is, given a state and an input, you can always deterministically transition to the next state.
DFAs have some interesting properties. For example, for complementation, you only need to swap the accept and non-accept states, and the new DFA is the complement of the original DFA. For example: determine whether a binary string is not divisible by 8. You can do it like this:
Moreover, just as in arithmetic we can always find a least common divisor, through certain algorithms we can always convert a DFA into a minimal DFA. I won’t elaborate here.
Let’s return to the divisibility-by-8 example. Can we express this FSM like this?
I don’t care how many characters are accepted at the beginning, but the last three must be 0, 0, 0. This formulation is very intuitive. However, generally speaking, what is intuitive to humans is not intuitive to machines. This is an NFA (Nondeterministic Finite Automaton). Given a state and an input, we cannot deterministically transition to the next state. For example, when the state is E and the input is 0, should it transition to state 0 or stay in its current state? Who knows?
The Master said: To transit or not to transit, this is a question.
To deal with an NFA, we can only use a decision tree—wherever one input may produce multiple states, we split into as many paths as there are output states. Then, when all paths have ended (either the input is exhausted or a path is stuck in some state and cannot proceed), as long as one path reaches an accept state, the input satisfies the NFA. For example, the two inputs 1000 and 1001:
The former succeeds; the latter fails.
Of course, this is not optimal in terms of processing efficiency: the paths in the decision tree grow exponentially with the number of states that carry nondeterminism. So most of the time, we convert the NFA to a DFA, and then convert the DFA to a minimal DFA.
What is the NFA good for? One important use case is regular expressions (regex). A regex is a simple language (or expression) for describing pattern matching; most programmers cannot get through their daily work without it. The above problem can be expressed with the regex .*000. Early regex implementations were converted into NFAs, then into DFAs, ultimately processing input efficiently. Representative products that use FSMs to handle regex include awk, sed, and re2.
But modern regexes are no longer pure (non-regular). In particular, support for backreferences means they cannot be expressed with an NFA—they are not even context-free. Take this regex for matching palindromes: (.+)\1 (it can match “tyrtyr”). For a while I was a regex fanboy—the kind who, holding a hammer, sees every problem as a nail—and I often wrote regexes that were either baffling or insanely complex. I won’t talk about the complex ones; here’s one that is baffling but fun:
(.+)(.+)(.+)(.+)(.+).*?\5\4\3\2\1Guess what it does.
Regexes like this are very troublesome to process: you need to be able to stop, backtrack, and have extra space to record captured groups. The product that handles such things, having gone beyond the scope of regex, is the famous string-search artist: PCRE. Today many languages’ regex libraries use PCRE directly (for example, Elixir; but early Python did not, and Go uses its own official re2).
A quick complaint: PCRE is extremely complex—so complex that it has its own JIT. For a comparison of the performance of tools that implement regex in different ways, see this comparison: http://sljit.sourceforge.net/regex_perf.html.
That’s as much FSM theory as we’ll cover.
FSMs are mainly applied in event-based processing. In general, if a system, while in some state, receives certain information and after processing produces a new state, it can be implemented using the FSM approach. The most typical use cases are network protocols, such as OSPF (the bulk of RFC 2328 describes state changes under various scenarios), as well as the TCP three-way handshake, FTP connection setup, and the handling of various commands.
There are also scenarios involving specific business domains, such as user progression systems (users migrating from registered user -> verified user -> profile-complete user -> core user), payment systems, and booking systems—all bear traces of FSMs.
