CS计算机代考程序代写 Slide 1

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