§11.2 – Finite State Machines
with Output
by Dr. Michael P. Frank, University of Florida
Modified by Longin Jan Latecki, Temple University
• Remember the general picture of a computer as
being a transition function T:S×I→S×O?
– If the state set S is finite (not infinite), we call this
system a finite state machine.
• If the domain S×I is reasonably small, then we can
specify T explicitly by writing out its complete
graph.
– However, this is practical only for machines that have a
very small information capacity.
Size of FSMs
• The information capacity of an FSM is
C = log |S|.
– Thus, if we represent a machine having an information capacity
of C bits as an FSM, then its state transition graph will have |S|
= 2C nodes.
• E.g. suppose your desktop computer has a 512MB
memory, and 60GB hard drive.
– Its information capacity, including the hard drive and memory
(and ignoring the CPU’s internal state), is then roughly
~512×223 + 60×233 = 519,691,042,816 b.
– How many states would be needed to write out the machine’s
entire transition function graph?
2519,691,042,816 = A number having >1.7 trillion decimal digits!
One Problem with FSMs as Models
• The FSM diagram of a reasonably-sized computer
is more than astronomically huge.
– Yet, we are able to design and build these computers
using only a modest amount of industrial resources.
• Why is this possible?
• Answer: A real computer has regularities in its
transition function that are not captured if we just
write out its FSM transition function explicitly.
– I.e., a transition function can have a small, simple,
regular description, even if its domain is enormous.
Other Problems with FSM Model
• It ignores many important physical realities:
– How is the transition function’s structure to be encoded
in physical hardware?
• How much hardware complexity is required to do this?
– How close in physical space is one bit’s worth of the
machine’s information capacity to another?
• How long does it take to communicate information from one
part of the machine to another?
– How much energy gets dissipated to heat when the
machine updates its state?
• How fast can the heat be removed, and how much does this
impact the machine’s performance?
Vending Machine Example
• Suppose a certain vending machine
accepts nickels, dimes, and quarters.
– If >30¢ is deposited, change is
immediately returned.
• If the “coke” button is pressed,
the machine drops a coke.
– It can then accept a new payment.
Ignore any other
buttons, bills,
out of change,
etc.
Modeling the Machine
• Input symbol set:
I = {nickel, dime, quarter, button}
– We could add “nothing” or  as an additional input
symbol if we want.
• Representing “no input at a given time.”
• Output symbol set:
O = {, 5¢, 10¢, 15¢, 20¢, 25¢, coke}.
• State set:
S = {0, 5, 10, 15, 20, 25, 30}.
– Representing how much money has been taken.
Transition Function Table
Old
state Input
New
state Output
Old
state Input
New
state Output
0 n
5 
10 n
15 
0 d
10 
10 d
20 
0 q
25 
10 q
30 5¢
0 b
0 
10 b
10 
5 n
10 
15 n
20 
5 d
15 
15 d
25 
5 q
30 
15 q
30 10¢
5 b
5 
15 b
5 
Transition Function Table cont.
Old
state Input
New
state Output
Old
state Input
New
state Output
20 n
25 
30 n
30 5¢
20 d
30 
30 d
30 10¢
20 q
30 15¢
30 q
30 25¢
20 b
20 
30 b
25 n
30 
25 d
30 5¢
25 q
30 20¢
25 b
25 
0 coke
Another Format: State Table
Old
state
Input Symbol
n
d
q
b
0
5,
10,
25,
0,
5
10,
15,
30,
5,
10
15,
20,
30,5¢
10,
15
20,
25,
30,10¢
15,
20
25,
30,
30,15¢
20,
25
30,
30,5¢
30,20¢
25,
30,10¢ 30,25¢
0,coke
30 30,5¢
Each pair shows
new state,
output symbol
Directed-Graph State Diagram
• As you can see, these can get kind of busy.
q,5¢
q
0
b
nd
5
b
n
10
b
d
n
d,5¢
q
15
n
b
b,coke
d
q,20¢
20 n 25 n 30
b
b
q,15¢
q,10¢
n,5¢
d,10¢
q,25¢
Formalizing FSMs
• Just like the general transition-function definition from
earlier, but with the output function separated from the
transition function, and with the various sets added in,
along with an initial state.
• A finite-state machine M=(S, I, O, f, g, s0)
–
–
–
–
–
–
S is the state set.
I is the alphabet (vocabulary) of input symbols
O is the alphabet (vocabulary) of output symbols
f is the state transition function
g is the output function
s0 is the initial state.
• Our transition function from before is T = (f,g).
Construct a state table for the finite-state machine in Fig. 3.
Find the output string for the input 101011
A unit-delay machine:
Construct a finite-state machine that
delays an input string by one unit of time:
Input:
x1x2 … xk-1xk
Output: 0x1x2 … xk-1
Language recognizer:
Construct a finite-state machine that outputs 1 iff
the input string read so far ends with 111.
Descargar

Slides for Rosen, 5th edition