FSM: Introduction
Consider the program we wrote for the example on this page. The logic behind the program was elementary. When we pressed the button, the LED would light up. To implement this functionality, we used a combinational logic (if-then-else) that purely depended on the current inputs. Now, imagine a complicated interactive application on your computer. Do you think a similar approach will work when implementing it?
When we are developing simple embedded systems, we are trying to automate a process and solve specific problems. Mathematicians and computer scientists have developed abstract models that can be very useful when solving these problems. An abstract machine is a theoretical model of computer hardware or software system. An entire branch of computational science is dedicated to automata theory, which is the study of automation and abstract machine models called automatons. The below figure shows four different abstract machines that can be used for solving computational problems.
At the top of the hierarchy of abstract machines is the Turing machine, which is very powerful but also rather complicated. Pushdown automaton is less powerful and less complex. Both of these automatons, however, are too complex for modeling the projects we encounter in this class. At the bottom of the hierarchy is the combinational logic. We used this model for the Button-LED project described earlier. This computational model is very basic and cannot solve problems as simple as building a stopwatch.
In short, the combinational logic model is too basic and very limited in the scope of problems it can handle. Pushdown automaton and Turing Machine, on the other hand, are too general and more complex than the requirements for most issues we deal with in this course. It turns out "Finite State Machine" is "just right" when it comes to many of the problems we are trying to solve in this class.