Finite State Machine Applications
Eric Gribkoff
May 29, 2013
Outline
1 Applications of Finite State Machines
2 Vending Machine
3 Pac-Man
4 TCP
5 Adding Output
Eric Gribkoff
|
UC Davis 2/11
1 Applications of Finite State Machines
• Vending Machines
• Traffic Lights
• Video Games
• Text Parsing
• CPU Controllers
• Protocol Analysis
• Natural Language Processing
• Speech Recognition
Eric Gribkoff
|
UC Davis 3/11
Eric Gribkoff
|
UC Davis 4/11
2 Vending Machine
$0.00
start
$0.25 $0.50 $0.75
$1.00
$1.25
$1.50
$1.75
$2.00
$0.25
$0.25 $0.25
$0.25
$0.25
$1.00 $1.00
$1.00
$1.00
$1.00
select select select select
select
$0.25, $1.00
$0.25, $1.00
$0.25, $1.00
$0.25, $1.00
select
select
select
select
Eric Gribkoff
|
UC Davis 5/11
3 Pac-Man
Eric Gribkoff
|
UC Davis 6/11
Wander the Maze
start
Chase Pac-Man
Return to Base
Flee Pac-Man
Spot
Pac-Man
Lose
Pac-Man
Pac-Man Eats
Power Pellet
Power Pellet
Expires
Pac-Man Eats
Power Pellet
Eaten by
Pac-Man
Reach
Central Base
Figure 1: Behavior of a Pac-Man Ghost
Eric Gribkoff
|
UC Davis 7/11
4 TCP
Eric Gribkoff
|
UC Davis 8/11
CLOSED
start
LISTEN
SYN_SENTSYN_RCVD
ESTABLISHED
FIN_WAIT_1
FIN_WAIT_2
CLOSE_WAIT
CLOSING
LAST_ACK
TIME_WAIT
Passive open
Close
SYN/SYN + ACK
Send/SYN
Timeout/RST
Close
Active open/SYN
SYN/SYN + ACK
Close/FIN
ACK
SYN + ACK/ACK
Close/FIN
FIN/ACK
ACK
ACK
FIN +
ACK/ACK
FIN/ACK
ACK
Close/FIN
ACK
Timeout after two maximum
segment lifetimes (2*MSL)
Figure 2: TCP State Diagram
Eric Gribkoff
|
UC Davis 9/11
5 Adding Output
Finite state machines with an output tape are known as finite state
transducers (FST). A Mealy machine is an example of a deterministic FST.
Instead of accepting or rejecting strings, a Mealy machine maps input
sequences to output sequences.
Eric Gribkoff
|
UC Davis 10/11
Next: Finite State Transducers