Mathematical Foundation of Computer Science

DHARM

240 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Assume that states r 0 , r 1 and r 2 are represented by symbol 0, 1 and 2 respectively, then
λ (r 0 ) = 0 ; λ (r 1 ) = 1 ; and λ (r 2 ) = 2 ;
FACT
l In the Moore machine, the first symbol in the output string always specified the start
state.
l In the Moore machine the output string has not the same length as the input string. If
we compare the length of input string with length of output string, then we found that
length of output string is one more than length of input string. So, if x is the input
string and w is its output string then,
| x | + 1 = | w |;
Since, it is assume that machine always starts from initial state. So, corresponding to
the start state an additional output symbol always comes in the list of output string.
While, in case of Melay machine length of the output string is no greater than the
input string.
l The language of a Moore machine doesn’t define on the basis of accepted word. Since,
every traceable input string generates some output string and there is no such thing as
final state. The process is terminated when the last symbol of input string is read and
the last output symbol is printed.
Note. Moore and Melay machines are Deterministic Finite State Automatons. Hence, from each
state of above machines, there is exactly one and only one exit transition arc on each input symbol.
Example 9.11. Consider the Moore machine shown in Fig. 9.34, determine the output for the
input string 10111.
Sol. From the start state r 0 , we obtain following sequence of states after reading the
input string 10111,

r 0 r 1 r 2 r 2 r 2

1

01222

Input string

Output string

r 2

2

01 11

Hence, the output string is 012222. If we carefully observe the nature of return string

then we will find that it is the reminder of 3. See the table shown in Fig. 9.35.

For the input string 010111

Input Symbol Equivalent Value Operation Output

(Value mod 3) (Reminder of 3)

0 0 0 mod 3 0

1 (01) 2 1 mod 3 1

0 (010) 2 2 mod 3 2

1 (0101) 2 5 mod 3 2

1 (01011) 2 11 mod 3 2

1 (010111) 2 23 mod 3 2*

Fig. 9.35