Finite-State Machine (FSM)
A Finite-State Machine (FSM) is an abstract machine that is composed of a finite set of state positions and a finite set of state transitions.
- AKA: Finite-State Automaton (FSA).
- Context:
- It can associate with a Regular Language (and its associated regular expressions)
- It can be the pattern used for: a Finite-State Sequence Tagging Model.
- It can range from being a Deterministic Finite-State Machine to being a Nondeterministic Finite-State Machine.
- It can be represented by a State Diagram.
- …
- Example(s):
- Counter-Example(s):
- See: Finite State Automaton String Matching Algorithm, Morphological Parsing Task, Model of Computation, Sequential Logic, State (Computer Science), Vending Machine, Elevator, Traffic Light, Combination Lock.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Finite-state_machine Retrieved:2015-1-16.
- A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model of computation used to design both computer programs and sequential logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition; this is called a transition. A particular FSM is defined by a list of its states, and the triggering condition for each transition.
The behavior of state machines can be observed in many devices in modern society which perform a predetermined sequence of actions depending on a sequence of events with which they are presented. Simple examples are vending machines which dispense products when the proper combination of coins is deposited, elevators which drop riders off at upper floors before going down, traffic lights which change sequence when cars are waiting, and combination locks which require the input of combination numbers in the proper order.
Finite-state machines can model a large number of problems, among which are electronic design automation, communication protocol design, language parsing and other engineering applications. In biology and artificial intelligence research, state machines or hierarchies of state machines have been used to describe neurological systems and in linguistics—to describe the grammars of natural languages.
Considered as an abstract model of computation, the finite state machine is weak; it has less computational power than some other models of computation such as the Turing machine. That is, there are tasks which no FSM can do, but some Turing machines can. This is because the FSM has limited memory. The memory is limited by the number of states.
FSMs are studied in the more general field of automata theory.
- A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model of computation used to design both computer programs and sequential logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition; this is called a transition. A particular FSM is defined by a list of its states, and the triggering condition for each transition.
2011
- (Wikipedia, 2011) ⇒ http://en.wikipedia.org/wiki/Finite-state_machine
- … A state describes a behavioral node of the system in which it is waiting for a trigger to execute a transition. Typically a state is introduced when the system does not react the same way to the same trigger. In the example of a car radio system, when listening to the radio (in the radio state), the "next" stimulus means going to the next station. But when the system is in the CD state, the "next" stimulus means going to the next track. The same stimulus triggers different actions depending on the current state. In some Finite-state machine representations, it is also possible to associate actions to a state:
- Entry action: which is performed when entering the state,
- Exit action: which is performed when exiting the state.
- A transition is a set of actions to be executed when a condition is fulfilled or when an event is received.
- … A state describes a behavioral node of the system in which it is waiting for a trigger to execute a transition. Typically a state is introduced when the system does not react the same way to the same trigger. In the example of a car radio system, when listening to the radio (in the radio state), the "next" stimulus means going to the next station. But when the system is in the CD state, the "next" stimulus means going to the next track. The same stimulus triggers different actions depending on the current state. In some Finite-state machine representations, it is also possible to associate actions to a state:
2003
- (Beesley & Karttunen, 2003) ⇒ Kenneth R. Beesley, and Lauri Karttunen. (2003). “Finite State Morphology." CSLI Publications