Links
| Wikipedia | Generation 5 | Princeton |
| Alexander Sakharov | UML Tutorial | Introductory essay |
| Introduction |
| Lecture Part 1 | Finite Automata | Deterministic Finite Automata |
A finite state machine (FSM) or finite state automaton, or simply a state machine, is a model of behaviour composed of a finite number of states, transitions between those states, and actions. It is similar to a "flow graph" where we can inspect the way in which the logic runs when certain conditions are met. A finite state machine is an abstract model of a machine with a primitive internal memory. (Wikipedia)
Define the function of these finite state machines:
A finite state machine has one tape from which symbols can be read and to which symbols can be written. This distinguishes a FSM from a FST or Finite State Transducer (see below).
Here is a FSM for a door. And one for reading the word nice. The word example shows that every correctly spelled word has a corresponding state machine which only moves to an acceptance state when the word is correctly spelled. All states of a FSM are either accepting (correct input) or non-accepting (incorrect input). A FSM that accepts a word is defining the language and a language that is accepted by a FSM is a regular language; or, to put it another way, a regular language is one for which a FSM exists. A FSM could also be used to analyse regular expressions (and here) such as email addresses.
Finite state machines are representations of 'machines' in the broadest sense: machines that have 'states', inputs and transitions between states. Designing and drawing a FSM is a useful or essential step in preparing a project that involves a machine that changes states, as most machines do: anything controlled by a switch has at least two states. A FSM is, in effect, a model of a product. FSMs can be applied to devices such as micro wave ovens, missile systems and vacuum cleaners as well as to computer programs. A FSM should have a start state to get the machine running.
Implement this in Turing Kara. You will need two states, S0 and S1, and a model that includes a suitable string of 0s and 1s. What is the purpose of this machine?
Here. This provides a strict definition of a FSM as a 5-tuple (has five parts: a finite set of states (Q); a finite set of input symbols (); a transition function; a start state (q0); a set of accept states that is a subset of Q).
A FSM will accept a given string if there is a sequence of states in Q such that the first state is the start state q0, the transition function will perform the transition between all the given states and the last input causes the machine to halt in an accepting state.
A transition function may be defined by a state table:
| 0 | 1 | |
| S1 | S2 | S1 |
| S2 | S1 | S2 |
In words, if 0 is received in S1 then go to S2, etc.
The language of this FSM can be summarised in a regular expression as: 1*(0(1*)0(1*))*. (* is the Kleene star and denotes 0, 1 or more of the designated character. So any number of 1s may be followed by a zero, which may be followed by any number of 1s, followed by a zero, followed by any number of 1s; this grouping may be repeated zero or more times.) The state transition diagram for the FSM shows this.
A simple example is traffic lights over a narrow bridge or through road works. In this case the 'inputs' are provided by a timer or, possibly, a sensor that detects when a vehicle approaches.
Assuming that the lights on both sides start in state 'Red', they will follow a timed sequence so that traffic can pass safely over the bridge. What condition needs to be applied to ensure that vehicles coming in opposite directions do not meet?
FSMs are drawn using nodes (circles) and edges (lines). Inputs that trigger changes of state are drawn over the edges, along with any outputs in the form
a | b, where a is the input and b is the output.
Draw a FSM for a simple set of traffic lights. One approach is to pair the lights on either side with a delay of a few seconds between states. How many states are there?
We can draw a pelican crossing FSM as a series of states. What distinguishes a pelican crossing from traffic lights?
Some nasty accidents occur at automatic level crossings (see here). Design a FSM for an automatic level crossing. (Also in B&L, pp 29-30)
You may by now have recognised that the examples studied so far are available as mimics in Flowol. Flowol uses a different representation for modelling machines with states and transitions (flow chart symbols). Flowcharts are similar to FSMs in that they produce a model of a machine that features inputs, outputs and transitions - that much has not changed in the design of machines.
The baby's mobile in Flowol features three inputs (blue, green, yellow buttons) and a number of outputs on the mobile (forwards, reverse, lights, propeller, rotors). Draw a FSM for the mobile. What assumptions will you make about the behaviour of the buttons? How many states do you want the mobile to be in at any one time? Start with a mobile with a single button, then two buttons and finally three. How many states are there for one button? for two or three?
This is a FSM with no outputs produced during processing. A FSA produces a result that is either Yes or No; the intervening steps are less important than the output so they are not given. The states that lead to a Yes result are called accepting states. Accepting states are denoted by a double ring, other states are represented by a single ring. Example page 31 of B&L.
A finite-state transducer (FST) is a finite state machine with two tapes: an input tape and an output tape. The two tapes of a transducer are typically viewed as an input tape and an output tape. On this view, a transducer is said to transduce (i.e., translate) the contents of its input tape to its output tape, by accepting a string on its input tape and generating another string on its output tape.
This contrasts with an ordinary finite state automaton, which has a single tape. Transducers generate output based on a given input and/or a state using actions. They are used for control applications and in the field of computational linguistics. Here two types are distinguished:
(Named after George Mealy). In a Mealy machine the FSM uses only input actions, i.e., output depends on input and state. In the example There are two input actions (I:): "start motor to close the door if command_close arrives" and "start motor in the other direction to open the door if command_open arrives". In a diagram for a Mealy machine outputs are shown on the transitions (arcs between nodes).
In the theory of computation, a Moore machine is a finite state transducer where the outputs are determined by the current state alone (and do not depend directly on the input). This type of FSM uses only entry actions, i.e., output depends only on the state. The state diagram for a Moore machine will include an output signal for each state. Compare with a Mealy machine, which maps transitions in the machine to outputs. Most digital electronic systems are designed as clocked sequential systems. Clocked sequential systems are a restricted form of Moore machine where the state changes only when the global clock signal changes. Typically the current state is stored in flip-flops, and a global clock signal is connected to the "clock" input of the flip-flops. (Wikipedia)
A further distinction is between deterministic (DFA) and non-deterministic (NDFA, GNFA) automata. In deterministic automata, for each state there is exactly one transition for each possible input. In non-deterministic automata, there can be none, one, or more than one transition from a given state for a given possible input. This distinction is relevant in practice, but not in theory, as there exists an algorithm which can transform any NDFA into an equivalent but much more complex DFA. (Wikipedia)
Example on page 33 of B&L. Consider how a word processor checks spelling as you type. As letters are entered the number of words that the current word could be is reduced. After 1 letter there are tens of thousands of possibilities; after two letters the number of possibilities is reduced and so on until the word is completed by pressing space. If the word is not recognised it will be underlined. There might be a FSM for every word in the dictionary but this would take up a lot of space. An alternative approach is to use a non-deterministic approach where the next letter can be one of 26 possibilities (in English at least, more in many other languages).
Kara provides a way of building FSMs. See here.
