324 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13
(6) Output functiong:S×A→Zdefined by:g(s 0 ,a)=x, g(s 1 ,a)=x, g(s 2 ,a)=z
g(s 0 ,b)=y, g(s 1 ,b)=z, g(s 2 ,b)=yState Table and State Diagram of a Finite State Machine
There are two ways of representing a finite state machineMin compact form. One way is by a table called
thestate tableof the machineM, and the other way is by a labeled directed graph called thestate diagramof the
machineM.
The state table combines the next-state functionfand the output functionginto a single table which represent
the functionF:S×A→S×Zdefined as follows:
F(si,aj)=[f(si,aj), g(si,aj)]For instance, the state table of the machineMin Example 13.1 is pictured in Fig. 13-1(a). The states are listed
on the left of the table with the initial state first, and the input symbols are listed on the top of the table. The entry
in the table is a pair(sk,zr)wheresk=f(si,aj)is the next state andzr=g(si,aj)is the output symbol. One
assumes that there are no output symbols other than those appearing in the table.
Fig. 13-1The state diagramD=D(M)of a finite state machineM=M(A,S,Z,s 0 ,f,g)is a labeled directed graph.
The vertices ofDare the states ofM. Moreover, if
F(si,aj)=(sk,zr), or equivalently,f(si,aj)=sk and g(si,aj)=zrthen there is an arc (arrow) fromsitoskwhich is labeled with the pairaj,zr. We usually put the input symbolai
near the base of the arrow (nearsi) and the output symbolzrnear the center of the arrow. We also label the initial
states 0 by drawing an extra arrow intos 0. For instance, the state diagram of the machineMin Example 13.1
appears in Fig. 13-1(b).
Input and Output Tapes
The above discussion of a finite state machineMdoes not show the dynamic quality ofM. SupposeMis
given a string (word) of input symbols, say
u=a 1 a 2 ...amWe visualize these symbols on an “input tape.” The machineM“reads” these input symbols one by one and,
simultaneously, changes through a sequence of states
v=s 0 s 1 s 2 ...sm