Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 325

wheres 0 is the initial state, while printing a string (word) of output symbols

w=z 1 z 2 ...zm

on an “output tape.” Formally, the initial states 0 and the input stringudetermine the stringsvandwas follows,
wherei= 1 , 2 ,...,m:

si=f(si− 1 ,ai) and zi=g(si− 1 ,ai)

EXAMPLE 13.2 Consider the machineMin Fig. 13-1, that is, Example 13.1. Suppose the input is the word

u=abaab

We calculate the sequencevof states and the output wordwfrom the state diagram as follows. Beginning at the
initial states 0 we follow the arrows which are labeled by the input symbols as follows:

s 0

a,x

−−→s 1

b,z

−→s 1

a,x

−−→s 2

a,z

−→s 0

b,y

−−→s 2

This yields the following sequencevof states and output wordw:

v=s 0 s 1 s 1 s 2 s 0 s 2 and w=xzxzy

Binary Addition

This subsection describes a finite state machineMwhich can do binary addition. By adding 0’s at the
beginning of our numbers, we can assume that our numbers have the same number of digits. If the machine is
given the input
1101011

• 0111011

then we want the output to be the binary sum 10100110. Specifically, the input is the string of pairs of digits to
be added:
11 , 11 , 00 , 11 , 01 , 11 , 10 ,b

wherebdenotes blank spaces, and the output should be the string:

0 , 1 , 1 , 0 , 0 , 1 , 0 , 1

We also want the machine to enter a state called “stop” when the machine finishes the addition.
The input symbols and output symbols are, respectively, as follows:

A={ 00 , 01 , 10 , 11 ,b} and Z={ 0 , 1 ,b}

The machineMthat we “construct” will have three states:

S={carry(c),no carry(n),stop(s)}

Herenis the initial state. The machine is shown in Fig. 13-2.

In order to show the limitations of our machines, we state the following theorem.

Theorem 13.1: There is no finite state machineMwhich can do binary multiplication.

If we limit the size of the numbers that we multiply, then such machines do exist. Computers are important

examples of finite state machines which multiply numbers, but the numbers are limited as to their size.