— Ch. 1 · Foundations And Definitions —
Finite-state machine.
~4 min read · Ch. 1 of 7
A finite-state machine exists as a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The system changes from one state to another in response to some inputs. This change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types, deterministic finite-state machines and non-deterministic finite-state machines. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.
Real World Mechanisms
Consider a coin-operated turnstile used to control access to subways or amusement park rides. A turnstile is a gate with three rotating arms at waist height. Initially the arms are locked, blocking entry and preventing patrons from passing through. Depositing a coin or token in a slot on the turnstile unlocks the arms. This allows a single customer to push through. After the customer passes through, the arms lock again until another coin is inserted. The turnstile has two possible states: Locked and Unlocked. There are two possible inputs that affect its state: putting a coin in the slot and pushing the arm. In the locked state, pushing on the arm has no effect. Putting a coin shifts the state from Locked to Unlocked. In the unlocked state, putting additional coins has no effect. A customer pushing through resets the state to Locked.Classification Systems
Finite-state machines can be subdivided into acceptors, classifiers, transducers, and sequencers. Acceptors produce binary output indicating whether received input is accepted. Each state of an acceptor is either accepting or non-accepting. Once all input has been received, if the current state is an accepting state, the input is accepted. Otherwise it is rejected. An example shows an acceptor that accepts the string nice. In this acceptor, the only accepting state is state 7. Classifiers are a generalization of acceptors that produce n-ary output where n is strictly greater than two. Transducers produce 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. Sequencers have a single-letter input alphabet and produce only one sequence.