automata

 Finite state machine

A finite state machine (FSM) or finite state automaton (plural: automata) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an abstract model of a machine with a primitive internal memory.

 Start state

The start state is usually shown drawn with an arrow "pointing at it from nowhere" (Sipser (2006) p.34).

[edit] Accept state

Fig. 3: A finite state machine that determines if a binary number has an odd or even number of 0s.

An accept state (sometimes referred to as an accepting state) is a state at which the machine has successfully performed its procedure. It is usually represented by a double circle.

An example of an accepting state appears on the right in this diagram of a deterministic finite automaton (DFA) which determines if the binary input contains an even number of 0s.

S₁ (which is also the start state) indicates the state at which an even number of 0s has been input and is therefore defined as an accepting state. This machine will give a correct end state if the binary number contains an even number of zeros including a string with no zeros. Examples of strings accepted by this DFA are epsilon (the empty string), 1, 11, 11..., 00, 010, 1010, 10110 and so on.

 Transducers

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:

Moore machine

The FSM uses only entry actions, i.e., output depends only on the state. The advantage of the Moore model is a simplification of the behaviour. Consider an elevator door. The state machine recognizes two commands: "command_open" and "command_close" which trigger state changes. The entry action (E:) in state "Opening" starts a motor opening the door, the entry action in state "Closing" starts a motor in the other direction closing the door. States "Opened" and "Closed" don't perform any actions. They signal to the outside world (e.g., to other state machines) the situation: "door is open" or "door is closed".