Finite State Machines
Contents
Definition
A finite state machine is a way of breaking down a problem into several mutually independent states that are only able to change when a transition occurs. A transition occurs when an input is given. The machine can only be in one state at a time. The state the machine is in at any time is referred to as the '"current state'". Any change to the state is known as a "'transition'".
A finite state machine is not a physical machine. It is an abstract representation of an algorithm, showing how something changes in response to inputs or events. It is used to design computer programs and some logic circuits.The machine also enables it to check if the input is valid. This means that it has a wide variety of practical uses. One of these is a vending machine, which requires a valid input to determine what product is dispensed. Any input that is invalid will simply be rejected.
Where are they used:
- Robotics
- Video games industry
- Design of digital hardware systems
- Design of compilers and network protocols
- Definition of languages, and to decide whether a particular word is allowed in a language
Representing Finite State Machines
Finite state machines can be represented as diagrams.
Another way of representing Finite State Machines is through State Transition Tables. A State Transition Table lists all possible current states, all valid inputs that that particular state may receive, as well as what state the resulting transition leads to.
Finite State Automaton
A finite state automaton is a finite state machine which has no output. It has a start state and a set of end/accept states. If the automaton can reach an end state then the input is accepted.
Mealy Machines
A finite state machine with an output is called a Mealy Machine. It will output a value based on the input. Transitions are usually labelled with both input and output. Complex Mealy Machines can have both multiple inputs and outputs. This means they can be designed to create ciphers.
