SD03 - Finite State Machines 2

Question 1

A formal representation of an FSM is F = (S, σ, I, O, f, g)

What does the S represent?

Answer 1

The set containing all of the machine’s states

Question 2

A formal representation of an FSM is F = (S, σ, I, O, f, g)

What does the σ represent?

Answer 2

The initial state of the machine

Question 3

A formal representation of an FSM is F = (S, σ, I, O, f, g)

What does the I represent?

Answer 3

The input alphabet.

All of the possible characters the machine can take as input.

Question 4

A formal representation of an FSM is F = (S, σ, I, O, f, g)

What does the O represent?

Answer 4

The output alphabet.

All of the possible characters the machine can output.

Question 5

A formal representation of an FSM is F = (S, σ, I, O, f, g)

What does the f represent?

Answer 5

The next state function
The function maps from a state from S and a character from I as input to a state from S as output:
f : (S, I) → S

Question 6

A formal representation of an FSM is F = (S, σ, I, O, f, g)

What does the g represent?

Answer 6

The output function
The function maps from a state from S and a character from I as input to a sequence of characters from O as output:
g : (S, I) → O*

Question 7

What does orthogonality mean?

Answer 7

No information is duplicated, everything we need is specified exactly once

Question 8

What is the formal presentation of a finite-state machine?

Answer 8

F = (S, σ, I, O, f, g)