Finite State machines Flashcards
What is a finite state machine
A machine that has a finite number of states. With a set amount of inputs and outputs.
They can define what is solvable on a computer
2 types of Finite State machine
Moore and Mealy machines
What is the difference between Moore and Mealy machine
Mealy: Produces outputs during transmission
Moore: Produces outputs on arrival
2 ways to represent a FSM
A State Transition Diagram, State Transition Table
What are the different States
Accepting state: One that returns a yes after all inputs
Halting state: A state with no outgoing transitions
What is a deterministic algorithm
Only one possible state to move to when given an input
What is a non-deterministic algorithm
More than one state that can be transitioned to with one input
What is a Finite State Automaton
A FSM with no outputs.
