Finite State Machines

This topic will appear not to be mathematical in nature to many people, but that is a misconception. I suspect that the most common reason for this misconception and other similar ones, is that many people confuse mathematics with arithmetic, statistics, geometry or trigonometry. It is true that these topics are part of mathematics. They are not by any means an exhaustive list of mathematical topics. In fact, most mathematical topics have very little to do with arithmetic, statistics etc. In this case, the field in question is the theory of computation and complexity; a part of mathematics which mostly has applications in computer science.

A finite state machine (FSM) is at the same time a mathematical structure, a simple type of computer and a language checker. Formally, it is composed of five parts. These are:
a) An alphabet. This is the collection of all symbols that can be passed into the machine. It can be the Latin alphabet, the numbers 0 and 1, or any other predetermined set of symbols.
b) A set of states. These are abstract states the machine can be in. Since these machines generally relate to a physical model, the states will have some meaning.
c) An initial state. This is how the machine starts out, before any input is given.
d) A transition function. This tells the machine how to change its state according to each new input.
e) A set of final states. When the input stops, if the machine is in a final state, we say that the input was accepted. If on the other hand, a certain input ends with the machine at a non-final state, we say that the input was rejected.

To illustrate all this, I will give two common examples. The first one is for an automatic door. Let's say you have an automatic door. For simplicity, its states will be "Closed" and "Open". The "alphabet" will be an input of "0" if no one is within a small area around the door and "1" if there is someone in this area. The initial state will be "Closed". The transition function is as follows: If the input is 0 and the door is open, close it. If the input is 1 and the door is closed, open it. Otherwise, make no changes. Finally, we can say that both our states are acceptable final states, again for simplicity. As you see, this FSM models our automatic door fairly well. The question arises, why do we need this model? The answer is: Because this is how the door can be made automatic. By making this model, we can create the appropriate digital control system, which will be used to make the door work in this way. In fact, the actual electronics involved in making the automatic door work, are nothing more than a finite state machine, although it will be a more complex one than our simplistic model here.

The second example deals with numbers. We want to make a machine that will take in strings of zeroes and ones as input (I keep using this as my alphabet, because this is essentially how computers work; with 0s and 1s) and accept those strings that end in 1; this corresponds to accepting odd integers. To do this, we define our start state (0) and our final state (1). These are enough for the purpose of this simple machine. Our transition function will be: Move to the state which is the same as the symbol we entered. That is, if the most recent symbol is a 0, go to state 0. If it is a 1, go to state 1. Here, if a string is given in that ends in a 0, our machine will finish in state 0, which is not a final state. So the string will be rejected. Our machine only accepts the strings that end in a 1.

You may think that the second example has little to do with a physical model, compared to the door example before it. This is only partly true. The second example helps us understand a very important concept in the fields of mathematics, computer science and linguistics; that of language and grammar. Formally, languages and grammars can be separated into groups, according to their machine complexity. The grammar above ("all strings of 0s and 1s that end in 1) belongs to the group of languages, which can be formally defined by a FSM. These are known as "regular" or Type-3 grammars. Other grammars require more complex machines, in order to be defined. For example, we have the Type-2 or "context-free" grammars, which can be defined by a type of machine called a "Push-down automaton" or PDA. This is a more complicated machine than the FSM, as it also involves an additional structure, known as a stack, which helps maintain some history of the input, as opposed to the FSM, which only knows its current state.

I would like to end by pointing something very important out. Everything I said above may sound extremely theoretical, but it is vital for the design of personal computers. As you are probably viewing this blog on some machine that can access the internet and decode hypertext into readable text, it is safe to assume that your machine contains any number of these FSMs, PDAs and other, even more complicated computational structures. Without these, it would be impossible for your computer to do all the amazing things it does.