Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 237

The Melay machine shown in Fig. 9.29 is the 1’s complement machine where Me = ({q 0 },
{0, 1}, {0, 1}, δ, λ, q 0 } and δ and λ are defined as,
δ(q 0 , 0) = q 0 ; δ(q 0 , 1) = q 0 ;
and λ(q 0 , 0) = 1; λ(q 0 , 1) = 0;
For example if the input string is 1010110 then Me generates corresponding output
string 0101001 (1’s complement of the string 1010110).

Example 9.9.

q 0

q 1

q 3

0/1

0/1

1/0

0/0, 1/1

1/0
Fig. 9.30 Me.
Melay shown in Fig. 9.30 is an incremental machine. For example, if the input string is
1000 the return string will be 1001, if input string is 0000 then we get the output string 0001,
provided that the symbol read from the input string is from right to left.
Input string 1 0 0 0 , 0 0 0 0 1 0 1 0 1 1

Output string 1 0 0 1 0 0 0 1 1 0 1 1 0 0

Example 9.10. Construct the Melay machine that accepts the string x and returns string 3
times of x, where string x is formed over Σ = {0, 1}.
Sol. Consider any string of 0’s and 1’s i.e., x = 0101 then output will be 3 times the number
represented by binary digits 0101, that will be 1111 i.e.,
Input string 0 1 0 1 or, 0 0 0 1 1 1

Output string 1 1 1 1 0 1 0 1 0 1
Procedure to calculate3x
3 x can be calculated from x by simple three times addition of x like as,
x

• x
  x
  3 x
  For example, if x = 000111 calculation for 3x by step-by-step three times binary addi-
  tion will be given as,

000111

000111

000111

000101

00 01 10 10 01 00 ¬Position of Input Carry

Input string

Output string

Move in this direction