What is a finite-state machine?
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.
Questions about Finite-state machine
Short answers, pulled from the story.
How does a coin-operated turnstile function as a finite-state machine?
The turnstile has two possible states: Locked and Unlocked. In the locked state, putting a coin shifts the state from Locked to Unlocked, while pushing the arm resets the state to Locked.
What are the four types of finite-state machines?
Finite-state machines can be subdivided into acceptors, classifiers, transducers, and sequencers. Acceptors produce binary output indicating whether received input is accepted, while transducers produce output based on a given input and/or a state using actions.
Why do finite-state machines have less computational power than Turing machines?
The limitation exists because an FSM's memory is limited by the number of states it has. A finite-state machine has the same computational power as a Turing machine restricted to read operations only.
Which algorithm optimizes a finite-state machine with the minimum number of states?
The fastest known algorithm doing this is the Hopcroft minimization algorithm. Other techniques include using an implication table or the Moore reduction procedure.