Finite State Machines Flashcards
What is a finite state machine
A machine which consists of a finite set of possible states, with a set of allowable inputs that can change the state, and set of possible outputs
How do FSMs define what is solvable on a computer
If a problem is solvable by a computable algorithm then an FSM can be constructed from it and vice versa
What are the two FSMs which produce outputs
Moore, Mealy
What is a Mealy Machine(FSM)
An FSM which takes an input and produces an output as it transitions between states
What is a Moore Machine(FSM)
An FSM which takes an input and produces an output on arrival to a new state rather than on the transition
What are the two visual ways to represent an FSM
State transition diagram, State transition table
What is an accepting state(FSM)
A state that returns YES if it is reached after all inputs are consumed
What is a halting state(FSM)
A state with no outgoing transitions
What is a finite state automaton
A type of FSM that only provides a YES/NO, that it either rejects or accepts the input(s). No outputs.
What is a deterministic algorithm(FSM)
One who’s behaviour is completely determined by its inputs and the sequence of its instructions
What is a Non deterministic algorithm(FSM)
One which the outcome cannot be predicted with certainty even if the inputs are known
What is a state transition diagram
The model consisting of a circle for each state, arcs for transitions, and 2 concentric circles for accepting/halting states
What is a state transition table
A tabular version of a state transition diagram
What is the input alphabet(FSM)
The possible inputs to an FSM, also called triggers
What is the Output alphabet(FSM)
The possible outputs of an FSM
