Mathematical Foundation of Computer Science

DHARM

238 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Now assume that these carry positions represent three different states such that initially
automaton is in state C 00 , on symbol 1 automaton reaches to state C 01 and return the symbol 1.
For next input symbol 1, return output symbol is 0 and automaton reach to state C 10. This
state remains unchanged, if next input symbol will be 1 and return symbol is 1. At this state
(digit position) if input symbol is 0 then, return symbol will be 0 and next state will be C 01. At
this state if input symbol is 0 then automaton reach to state C 00 and produce output symbol 1.
State C 00 remains same for input symbol 0 and it outputted the symbol 0. Thus we obtain the
Melay machine shown in Fig. 9.31.

C 00 C 01 C 10

1/1

0/1

1/0

0/0

0/0

Fig. 9.31

We can verify the correctness of the above Melay machine over any input string of 0’s

and 1’s, i.e., for example x = (001011) 2 or (11) 10 , then machine should generate the output

string 3x that is (100001) 2 or (33) 10.

001011

001011

01 10 01 10 01 (^00) ¬Position of Input Carry
Input symbols
Output symbols
Symbols processed in this direction
000111
100001
Hence Melay machine works correctly and returns the 3 times of the input string. The
moves between states over input symbols and the generation of the output symbols are shown
in table shown in Fig. 9.32.
Current State Input Symbol Output Symbol Carry Generated State Transition
C 00 110 1C 00 → C 01
(No Carry)
C 01 101 0C 01 → C 10
C 10 000 1C 10 → C 01
C 01 101 0C 01 → C 10
C 10 000 1C 10 → C 01
C 01 010 0C 01 ® C 00
Fig. 9.32

9.6.2 Moore Automaton...............................................................................................

As we seen that, in the case of Melay machine (finite automata with output), the transition arc

between the states is labelled with a compound symbol such that the output is generated

corresponding to input symbol. In case of Moore machine output is represented by the state

itself. The names of the states are such, that it represents the output symbols. So, in case of

Moore machine, the output is associated with the states. Therefore, for a given input the