Finite Control Flashcards
What is Finite Control?
Problem that can be solved using a machine with a finite number of states
What is finite control redux?
The simplest case, finite control with no states
What is a state machine?
A state machine maps inputs to outputs
The mapping is determined by the state of the machine
What is the abstraction of a black box system?
Inputs
Outputs
State
What is the state of a machine?
What the machine will do with the next input
What is a finite state machine?
A machine, typically black box, that we know has a finite number of states. It maps a sequence of inputs to a sequence of outputs.
What are the three ways you can describe a FSM?
Graphically
Transition Tables
Mathematically
What is a formal system?
Mathematical description that defines a machine and how it works, no human intervention is needed after the definition
Benefits of the graphic representation of FSM
Intuitive
For people
Easily understood
Suggestive
Benefits of transition table representation of FSM
Complete
Simple
For computers
Drawbacks of transition table representation of FSM
Boring
Tricky when large
Drawbacks of graphic representation of FSM
Hard to translate into computers
Benefits of mathematical representation of FSM
Illuminate some things clearly
Capture everything
What are the six things needed to fully describe a FSM?
S - states o - initial/starting state I - input alphabet O - output alphabet f - next state function g - output function
What is orthogonality
The process of making sure there is no duplication, everything we need is specified once
What is a finite state automata?
A type of FSM that recognises and accepts/rejects input strings rather than generating output
What is the difference in the description of a FSA to a FSM?
A instead of O and g
accepting states
What is non determinism?
The process of allowing multiple transitions per letter
Describe nFSAs
Type of FSA that accepts string if there is any path through it it that would have accepted the string
Always a plain FSA alternative
What is an epsilon move?
A silent move that transitions without input
What are some combinators that are used to combine FSAs together?
Alternative
Repetition
Sequence
