Slide 1
Chapter 5
Finite State Machines
Transducers
Deterministic Finite State Transducers
A Moore machine M = (K, , O, , D, s, A), where:
● K is a finite set of states
● is an input alphabet
● O is an output alphabet
● s K is the initial state
● A K is the set of accepting states,
● is the transition function from K to K,
● D is the output function from K to O*.
M outputs each time it lands in a state.
A Moore machine M computes a function f(w) iff, when it reads the input string w, its output sequence is f(w).
A Simple US Traffic Light Controller
Deterministic Finite State Transducers
A Mealy machine M = (K, , O, , s, A), where:
● K is a finite set of states
● is an input alphabet
● O is an output alphabet
● s K is the initial state
● A K is the set of accepting states
● is the transition function from K to K O*
M outputs each time it takes a transition.
A Mealy machine M computes a function f(w) iff, when it reads the input string w, its output sequence is f(w).
An Odd Parity Generator
After every four bits, output a fifth bit such that each group of four bits has odd parity.
0 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1
input / output
A Bar Code Scanner
*
Single black line is a 0. Double black line is a 1.
A Bar Code Scanner
English Morphology
0
5
1
2
3
4
5
6
7
8
9
0
0 51234567890