Difference between revisions of "Finite State Machines"
(→Mealy Machines) |
Calsayles23 (talk | contribs) |
||
| Line 1: | Line 1: | ||
{{Need_Expanding}} | {{Need_Expanding}} | ||
== Definition == | == 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. | + | 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. | ||
== Finite State Automaton == | == Finite State Automaton == | ||
| Line 18: | Line 17: | ||
== 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. | + | 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 22:51, 4 January 2017
This section needs expansion.
You can help by adding to it.
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.
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.
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.
