How is a state machine different from any other computer program?

Question

I have seen several implementations of "State Machines" on github. As far as I understand, a state machine takes input that may or may not transform its state into one of a finite set of other states. How is that different from any other computer program?

Answer 1

If you want to be really pedantic, every computer program is a Finite State Machine, because even if you convert all matter in the entire universe into a computer, it will still only have finite memory, thus a finite amount of states, and a finite amount of transitions between those states.

State Machines are models, just like Lambda Calculus, Turing Machines, Random-Access Machines, Actor Systems, Object Systems, and so on. Some problems lend themselves to being modeled by a state machine, some don't.

Business Processes were often modeled as State Machines even before computers existed. They lend themselves naturally to that kind of thinking.

Answer 2

From a theoretical point of view, it's not different at all. Of course, from a theoretical point of view you can write any program in assembly language and it'll work just as well.

While the computer your code is running on may be mathematically equivalent to a very, very complicated state machine, as is any other program that runs on any other computer, there are many problems whose most elegant solution is a simple finite state machine whose states and transitions have domain-specific meanings that the programmer came up with (as opposed to the compiler or the hardware designer).

For instance, one classic way of implementing regular expressions is to interpret the regular expression as a specification for a finite state machine, build such a machine, then feed it strings to accept or reject. More generally, any time you want an object in your program to always have one of a finite number of states, and enforce that transitions between those states always happen in specific ways, building a state machine might be the most elegant solution.

Answer 3

a state machine takes input that may or may not transform its state into one of a finite set of other states. How is that different from any other computer program?

Some answers here emphasise that in our (probably) finite universe everything is finite, all computer programs run in finite time, therefore technically everything is a finite-state machine. That's "technically correct (the best kind of correct)", but also completely missing the point.

The essence is this: -- Some computer programs require more working memory when they get larger and more complex inputs. Some don't.

If you realize this, you will get a theoretical-informatical insight that may allow you to write more efficient and elegant programs when you encounter the given kind of problem. It will also allow you to recognize the kind of problem where this may apply.

Here are two toy examples:

Problem 1: A program receives a list of characters on standard input. After all characters are processed, the program must print whether the number of "x" characters in the input was odd or even.

Problem 2: A program receives a list of characters on standard input. After all characters are processed, the program must print whether the number of "x" characters in the input was smaller, equal, or greater than the number of "y" characters.

You may want to stop reading now, solve the problems in your favorite programming language (or just a pseudocode), and return later.

...

The important thing you may have noticed is the following: To implement the solution to problem 1 properly, you only need one bit of memory. You don't have to calculate how many "x"'s you have already processed -- only whether the number of "x"'s processed so far was odd or even. When you encounter another "x", flip the bit. At the end of the program, look at the bit and print the answer.

Does your input contain dozen characters? Thousands of characters? Googolplex characters (hypothetically speaking, of course)? Does not matter; one bit of working memory will still be enough.

You cannot do the same thing with problem 2. When reading the characters, you have to remember the difference between the number of already processed "x"'s and "y"'s; otherwise you can't print the correct answer reliably. You may realize that you actually don't need to remember both the numbers of "x"'s and "y"'s -- only their difference, so far; one integer value that you will increase when you encounter another "x", and decrease when you encounter another "y" -- but still, if you decide to use e.g. 32 bits of memory to keep this value, you may get an input (several billions of characters long) that you cannot process correctly with the given limited amount of memory.

This is what we mean by saying that the problem 1 can be solved by a "state machine", and problem 2 cannot. A limited amount of memory is enough for an input of any size.

(Of course, you could also write an inefficient solution to the problem 1, where you would try to count all the "x"'s, and then you might also get an out-of-memory problem. But the difference is that an efficient solution to the problem 1 exists, while a similarly efficient solution to the problem 2 does not.)

Why is this important in real life?

First, unlike with these two toy examples, the dilemma may not be between literally one bit and one integer value, but between some large and some even larger data structure. Sometimes the "even larger" data structure does not fit in the computer memory, or sufficiently slows down the program, even for realistic inputs.

Second, the solution using the state machine will probably be much faster. Also it will scale linearly with the length of input; that is, processing 10-times longer input will require 10-times more time (as opposed to e.g. 100-times more time). That's a desired property when you need to process a lot of data.

Third, limited vs unlimited memory usage has an impact on security. If you write a program that only requires limited memory, you don't have to worry about memory overflows and how they could potentially be abused to compromise the security of the whole system.

Fourth, this is part of what should be a standard computer science curriculum in any decent school: formal languages, authomata, computational complexity, et cetera. To understand the larger picture behind computer design, as opposed to merely "uhh, I put some pieces of code from internet together, I really hope it works, but I can't tell for sure" approach.

To take advantage of this theory, you don't really need any special machine, any framework or library... you only need to realize "oh, this part of the problem can actually be solved using a finite amount of memory" and write your program (in your favorite programming language) accordingly. But in some situations it is better to use an existing library, so you don't have to reinvent the wheel.

Answer 4

As the other answers pointed out, there is nothing special about state machines. However, it is frequently beneficial to explicitly state that our program implements a FSM.

Programming consists to a good deal of finding suitable abstractions for a problem. Using an abstraction implies speaking in terms of the abstraction rather than in terms of the implementation. Many processes are inherently stateful, for example the sign-up process on a website, or the check-out process in an e-commerce application. If I were to model those processes, I would draw boxes connected by arrows onto a whiteboard – a state diagram. Here, a state machine would be a kind of design pattern and talking about state machines would clearly communicate my intent to colleagues.

Imperative programs are inherently stateful so we don't always notice when we introduce state. E.g. in the C language, certain language constructs such as the semicolon operator mark a “sequence point”, which is a state transition and enforces ordering between operations. Things are different in environments such as pure functional languages such as Haskell or when using stateless protocols such as HTTP. Suddenly, any state must become explicit, and explicitly phrasing our design as a state machine can make it more manageable.

Finite state machines play an important role in parsing, since they correspond to regular expressions. Manually implementing some regular expression can result in extremely hairy code, which at its worst isn't even correct. When we realize that we are implementing a state machine, we can use a variety of known implementation techniques to help us. For example, we could make the state explicit and store the current state in a variable. Alternatively, we can make the state implicit through control flow on our language. I have done both in different circumstances, but stating that we are implementing a state machine (which features restricted state transitions, a start state, known end states, no recursion, and no implicit state through persistent data allocation) rather than an unrestricted program makes it easier to implement and understand.

I would rarely use a state machine library, since all programming languages I know make it easy to correctly and efficiently express a state machine in that language. But there are exceptions: while deterministic automata are easy to implement, nondeterministic automata are fairly nontrivial, since the state machine may be in multiple states at the same time. Using a library that implements NFAs or rewrites them lets me ignore these difficulties and focus on stuff that actually matters.

Beyond the uses of state machines as a design and state machines in computer science and language theory, there aren't really that many uses. Stateful logic circuits come to mind. The main use of state machines for a programmer is learning to think in terms of states and state transitions. Where does my program have implicit states? Did I correctly implement all state transitions? Did I miss something and open up an invalid state? Such thinking becomes especially relevant again in object-oriented programming, since the member fields of an object correspond to state, and methods may effect state transitions. I would hesitate to explicitly implement a state machine in an object, but a state machine can nevertheless be a suitable mental model for the behaviour.

The main reason to write a state machine library is to make sure you've understood the topic, but in most applications you would not need them or rather hand-roll them.