For example, lets say we want to build a finite state machine that can recognize strings of letters that start with a and are then followed by zero or more occurrences of the letter b or zero or more occurrences of the letter c terminated by the next letter of the alphabet. Non-deterministic finite state machines are finite state machines where a given input from a particular state can lead to more than one different state. This is an important concept when it comes to non-deterministic finite state machines.
It processes and then when it gets to the end, the state is read and something external triggers the desired action (dispenses a soda can, etc.). A state machine doesn’t do anything as it moves from state to state. It goes through all its processing and then the final state is read and then an action is taken. The output of a state machine is its final state. Well you kind of can with a state machine. What good is a set of decisions if the same input can result in moving to more than one state? You can’t tell a computer, if x=true then execute doSomethingBig or execute doSomethingSmall, can you? At first this sounds silly to even make this distinction. In other words there aren’t two paths leading out of a state when you read the letter a.
From any state there is only one transition for any allowed input. The state machines we’ve looked at so far are all deterministic state machines. If it successfully makes it to the final state, then you have those particular tags in the right order.įinite state machines can also be used to represent the mechanics of a parking meter, pop machine, automated gas pump and all kinds of other things. The state machine can move to state that shows it has read the html tag, loop until it gets to the head tag, loop until it gets to the head close tag, etc. A very simple example would be to determine if a page of HTML contains these tags in this order: This may sound pointless, but there are an awful lot of problems that can be solved with this type of approach. In our simple state machine above, if we end on s, the tape ends with the letter b, if we end on q, the tape ends with the letter a. Well it turns out that you can run a tape through the state machine and once it is done tell something about the sequence of letters by examining the state you end up on. Another b will keep us on s followed by an a which moves us back to the q state. So if we start on s and read the paper tape above from left to right, we will read the a and move to state q. So if you are in state s and read an a you’ll transition to state q. The circles are “states” that the machine can be in. For every inch of paper there is a single letter printed on it–either the letter a or the letter b.Īs the state machine reads each letter it changes state. Imagine a device that reads a long piece of paper. This sounds complicated but it is really quite simple. Each state specifies which state to switch for a given input. When it reads an input it will switch to a different state.
In simple terms, a state machine will read a series of inputs. Finite State MachineĪ finite state machine is a mathematical abstraction used to design algorithms. If there is interest I may follow up with some more advanced topics, but right now I want to look at the logic behind one of the simplest abstract computational devices–a finite state machine. The purpose of this article is to provide some fundamental background for computation.
However, if you plan to write code that requires serious computation, you are going to need to understand a bit more about how computation works under the hood. You don’t need to understand computational theory to build a “contact us” form in PHP. Much mundane everyday work that can be accomplished with little or no understanding of computer science. However, if you want to operate a car at the very limits of its capabilities, you need to know a lot more about automobiles than just the three pedals, gearshift and steering wheel. You can safely operate a car without having any clear idea of how it works. When we drive a car, we only concern ourselves with two or three pedals, a gearshift, and a steering wheel. When we program we work at a much higher level of abstraction. (If you like this, you should check out my cartoons on YouTube and my mailing list.)Ĭomputer science is what enables programming, but it is possible to do a lot of programming without understanding the computer science concepts underlying the process of computation.