Finite Control

Question 1

What is Finite Control?

Answer 1

Problem that can be solved using a machine with a finite number of states

Question 2

What is finite control redux?

Answer 2

The simplest case, finite control with no states

Question 3

What is a state machine?

Answer 3

A state machine maps inputs to outputs

The mapping is determined by the state of the machine

Question 4

What is the abstraction of a black box system?

Answer 4

Inputs
Outputs
State

Question 5

What is the state of a machine?

Answer 5

What the machine will do with the next input

Question 6

What is a finite state machine?

Answer 6

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.

Question 7

What are the three ways you can describe a FSM?

Answer 7

Graphically
Transition Tables
Mathematically

Question 8

What is a formal system?

Answer 8

Mathematical description that defines a machine and how it works, no human intervention is needed after the definition

Question 9

Benefits of the graphic representation of FSM

Answer 9

Intuitive
For people
Easily understood
Suggestive

Question 10

Benefits of transition table representation of FSM

Answer 10

Complete
Simple
For computers

Question 11

Drawbacks of transition table representation of FSM

Answer 11

Boring

Tricky when large

Question 12

Drawbacks of graphic representation of FSM

Answer 12

Hard to translate into computers

Question 13

Benefits of mathematical representation of FSM

Answer 13

Illuminate some things clearly

Capture everything

Question 14

What are the six things needed to fully describe a FSM?

Answer 14

S - states
o - initial/starting state
I - input alphabet
O - output alphabet
f - next state function
g - output function

Question 15

What is orthogonality

Answer 15

The process of making sure there is no duplication, everything we need is specified once

Question 16

What is a finite state automata?

Answer 16

A type of FSM that recognises and accepts/rejects input strings rather than generating output

Question 17

What is the difference in the description of a FSA to a FSM?

Answer 17

A instead of O and g

accepting states

Question 18

What is non determinism?

Answer 18

The process of allowing multiple transitions per letter

Question 19

Describe nFSAs

Answer 19

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

Question 20

What is an epsilon move?

Answer 20

A silent move that transitions without input

Question 21

What are some combinators that are used to combine FSAs together?

Answer 21

Alternative
Repetition
Sequence