Difference between revisions of "Finite State Machines"
| Line 12: | Line 12: | ||
#Design of compilers and network protocols | #Design of compilers and network protocols | ||
#Definition of languages, and to decide whether a particular word is allowed in a language | #Definition of languages, and to decide whether a particular word is allowed in a language | ||
| + | |||
| + | == 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. | ||
== Representing Finite State Machines == | == Representing Finite State Machines == | ||
Finite state machines can be represented as diagrams. | Finite state machines can be represented as diagrams. | ||
| − | [[File: | + | [[File:Fsmnotation.gif]] |
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. | 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. | ||
| − | + | [[File:Fsmdefinelanguage.gif]] | |
| − | + | ||
| + | This FSM defines the acceptable inputs of a language. If you start from the start state, and in correctly entering the input you finish on the accept/final state then the input is valid. However if no suitable path was possible, or you have run out of inputs before accessing the accept/final state, then the input is invalid. | ||
== Mealy Machines == | == 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. | 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. | ||
Revision as of 07:14, 22 May 2017
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
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.
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.
This FSM defines the acceptable inputs of a language. If you start from the start state, and in correctly entering the input you finish on the accept/final state then the input is valid. However if no suitable path was possible, or you have run out of inputs before accessing the accept/final state, then the input is invalid.
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.
