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 correct order.įinite state machines can also be used to represent many other systems - such as the mechanics of a parking meter, pop machine, automated gas pump, and all kinds of other things. The state machine can move to a 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, and so on. 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. If we end in state q, the tape ends with the letter ‘a’. In our simple state machine above, if we end in state s, the tape must end with a letter ‘b’. Well, it turns out that you can run a tape through the state machine and tell something about the sequence of letters, by examining the state you end up on. Then, we’ll read ‘b’ and move back to state s.Īnother ‘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. If you read a ‘b’, you’ll stay in state s. 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. A paper tape, with eight letters printed on itĪs the state machine reads each letter, it changes state. For every inch of paper there is a single letter printed on it–either the letter ‘a’ or the letter ‘b’. 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 to, for a given input. When it reads an input, it will switch to a different state. In simpler terms, a state machine will read a series of inputs. Finite State MachinesĪ 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 will 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. A lot of everyday work 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. Implementing a finite state machine is quite straightforward.By Mark Shead Understanding State Machines An intro to Computer Science conceptsĬomputer science enables us to program, but it is possible to do a lot of programming without understanding the underlying computer science concepts.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |