CS2001 W01

What is a computer?

Anything which can perform computation

What is an alphabet in terms of a FSM?

A finite set of symbols

What does Σ represent?

The input alphabet of a FSM

What does Γ represent?

The output alphabet of a FSM

What does ε represent?

The empty string

What does S represent?

A finite set of states in a FSM

What does s₀ represent?

The initial state of a FSM

What does a transition table describe?

The behaviour of a FSM

What does the output function do?

It describes the output for each (state, input) pair

ω : S X Σ —> (Γ ∪ {ε})

What does the transition function do?

It describes the next state for each (state, input) pair

δ : S X Σ —> S

What are the 3 ways that you can describe an FSM?

Transition table

6 tuple

graphically

What are the symbols in an FSM?