What state would you end up in if the input was the letter "a" repeated 100 times? People say that these inputs are "accepted" because they get you from the start state to the final state – it doesn’t have to be the shortest route. In the example above, the shortest input to get to state 2 is "a", but you can also get there with "aa", or "aba", or "baaaaa".
Usually the idea is to find a sequence of inputs that gets you from the start state to a final state. There's also a "start" state – that's the one with an arrow coming from nowhere. States could represent a mode of operation (like fast, medium, or slow when selecting a washing machine spin cycle), or the state of a lock or alarm (on, off, exit mode), or many other things.īy convention, this marks a "final" or "accepting" state, and if we end up there we've achieved some goal. What it actually means depends on what the FSA is being used for. This might seem pointless, but it can be quite useful.Įach of the "train stations" is called a state, which is a general term that just represents where you are after some sequence of inputs or decisions. Notice that this map has routes that go straight back to where they started!įor example, if you start at 1 and take route "b", you immediately end up back at 1. The map that we used above uses a standard notation. If there isn't a manual, you may find yourself wanting to draw a map, just as for the trains above, so that you can understand it better.
#FINITE STATE AUTOMATA MANUAL#
If there's a manual for the controller, it may well contain a diagram that looks like a finite state automaton. It might be a long journey back, and you may end up exploring all sorts of modes to get there! To get to the mode you want you have to press just the right sequence, and if you press one too many buttons, it's like getting to the train station you wanted but accidentally hopping on one more train. It might have half a dozen main buttons, and pressing them changes the mode of operation (e.g. If this occurs, it is an error in the design of the system – and it can be extremely frustrating for the caller!Īnother example is the remote control for an air conditioning unit. Sometimes you are taken round in circles because there is a peculiar loop in the finite state automaton. The dialogue can be quite simple, or very complex. Your key presses are inputs to a finite state automaton at the other end of the phone line.
You may have come across it when you dial a telephone number and get a message saying "Press 1 for this … Press 2 for that … Press 3 to talk to a human operator." People working with formal languages usually use finite state automata, but "FSAs" for short.Īn FSA isn't all that useful for train maps, but the notation is used for many other purposes, from checking input to computer programs to controlling the behaviour of an interface. Sometimes an FSA is called a finite state machine (FSM), or even just a "state machine".īy the way, the plural of "automaton" can be either "automata" or "automatons". "Automaton" is an old word meaning a machine that acts on its own, following simple rules (such as the cuckoo in a cuckoo clock).
The "state" is just as another name for the train stations we were using. "Finite" just means that there is a limited number of states (such as train stations) in the map. The name finite state automaton (FSA) might seem strange, but each word is quite simple.
0 kommentar(er)
