Mealy and moore machines

Exercises for the Finite State Machine unit

1. Finite State Revisited
A model of computation

2. What can a computer do?
•Models of computation strip specific
approaches down to a logical core
–Computable
–Not Computable
•Finite state machines are a simplified,
idealised model of a computing machine.
•Add permanent storage and you have a
Turing machine, the simplest general
computer

3. Three types of FSM
•Without output (answer true or false)
1.Finite State Automata
•With output
2.Mealy machine (output on transition)
3.Moore machine (output on state)

4. Software

5. Mealy and Moore
•Both have:
–No final state
–Produce output from an input string
–No non-determinism
•Mealy machines produce output on
transition
•Moore machines produce output on
state

6. Challenge 1
•Mealy machine that inverts the input.
•ie: if given 01101 outputs 10010

7. Challenge 2
•Mealy machine that divides by 2
•Ie: if given 0101 will give 0010

8. Challenge 3
•A Moore machine that inverts the input

9. Challenge 4
•Mealy Vending Machine
•5p, 10p, 20p – vends sweets at 15p –
gives change.

10. Challenge 5
•Moore machine to divide a binary
number by 2