Chapter 9: Finite-State Machines, Turing machines

Section 9.3 Finite-State Machines



finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation .A finite state machine is a mathematical abstraction used to design algorithms. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the 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.

A finite-state machine (FSM) is an abstract computational model used to design and describe systems with a finite number of states. It's a mathematical model that consists of a finite number of states, a set of inputs, a set of outputs, and a set of transitions between states based on inputs. FSMs are widely used in various fields such as computer science, engineering, and mathematics to model and control systems that have a finite number of states. FSMs are fundamental in understanding and designing systems with discrete states and transitions.


Finite state automata generate regular languages. Finite-state machines can be used to model problems in many fields including mathematics, artificial intelligence, games, and linguistics. parking meter, pop machine, automated gas pump, and all kinds of other things.

Example: coin-operated turnstile


The turnstile state machine can be represented by a state-transition table, showing for each possible state, the transitions between them (based upon the inputs given to the machine) and the outputs resulting from each input:

Formal Definition


Examples of Finite-State Machines

To describe a particular finite-state machine, we have to define the three sets and two functions involved.
Example 29:

FSM Examples in Daily Live

Practice



Reference

Wikipedia
Brilliant
FSM Exercise