Last Tech Tuesday, I presented the idea of a Finite State Machine (FSM) using a Nespresso machine as an example. We saw that what makes an FSM attractive is that we can easily analyze it using formal methods and answer such questions as to whether a particular state is ever reached or how long a computation by the machine will take. I also suggested though that this ability came at a price and today I want to explain that further.

To do that let’s start by looking at a common computer problem: recognizing a pattern. We will give ourselves a really simple problem by looking at strings that consist of only two letters “a” and “b”. Now we want to detect strings that have exactly one “b” in them. So our “language” includes the following words: “b”, “ab”, “ba”, “aab”, “aba”, “baa” … but does not include “”, “a”, “aa”, “bb”, “abb”, …

Here is a FSM that accepts this language, by which we mean for any string from the alphabet “a, b” the machine ends in one of two states which definitively tell us whether the string belongs to our language (ie has exactly one “b” in it) or does not:

Now here is something very important to observe. Our machine has only 6 states – clearly a finite number – in it but can handle arbitrarily long strings. We are not imposing any kind of upper boundary on the length of the strings for which we accept or reject and yet we only need a fixed number of states to make that decision. A language for which we can design an FSM that accepts it is called a regular language.

Now it turns out that regular languages are not all that expressive. Here is a simple example of a language over the same alphabet that is not regular: all palindromes. So for instance “abba” would be in the palindrome language but “abab” would not. Why is this not a regular language? Because we cannot design a finite state machine that accepts this language.

The reason has to do with memory. In our 6 state machine above the “Trailing a’s” state is different from the “Leading a’s” state because it embodies the memory of having encountered exactly one “b”. In order to recognize arbitrarily long palindromes we would have to be able to remember arbitrarily many letters that we have already encountered (to see if they are then repeated in reverse order). But that means we cannot have a finite number of states and hence no FSM can tell be used to determine whether something is a palindrome for arbitrarily long strings! Palindromes then are an example of a computing problem that FSMs are not sufficiently powerful to tackle (here is a formal proof).

So there we have it. We have bought our ability to formally analyze the FSM and be able to determine such things as whether a state is reached or how quickly it is reached by restricting the types of problems that we can compute with an FSM. This is an example of what I called computability – the study of what can (and cannot) be computed with a certain kind of machine. Next time we will look at the computational complexity aspect of a FSM.