CHAPTER 13 Finite State Machines and Turing Machines
13.1Introduction
This chapter discusses two types of “machines.” The first is a finite state machine (FSM) which is similar
to a finite state automaton (FSA) except that the finite state machine “prints” an output using an output alphabet
which may be distinct from the input alphabet. The second is the celebrated Turing machine which may be used
to define computable functions.13.2Finite State Machines
A finite state machine (or complete sequential machine)Mconsists of six parts:(1) A finite setAof input symbols. (4) An initial states 0 inS.
(2) A finite setSof “internal” states. (5) A next-state functionffromS×AintoS.
(3) A finite setZof output symbols. (6) An output functiongfromS×AintoZ.
Such a machineMis denoted byM=M(A,S,Z,s 0 ,f,g)when we want to indicate its six parts.EXAMPLE 13.1 The following defines a finite state machineMwith two input symbols, three internal states,
and three output symbols:
(1)A={a, b}, (2)S={s 0 ,s 1 ,s 2 }, (3)Z={x, y, z}, (4) Initial states 0 ,(5) Next-state functionf:S×A→Sdefined by:f(s 0 ,a)=s 1 ,f(s 1 ,a)=s 2 ,f(s 2 ,a)=s 0
f(s 0 ,b)=s 2 ,f(s 1 ,b)=s 1 ,f(s 2 ,b)=s 1323Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.