state machine

Problem 1. In the late 1960s, the military junta that ousted the government of the small republic of Nerdia completely outlawed built-in multiplication operations, and also forbade division by any number other than 3. Fortunately, a young dissident found a way to help the population multiply any two nonnegative integers without risking persecution by the junta. The procedure he taught people is: procedure multiply(x; y: nonnegative integers) r:= x; S:= y; a:= 0; while (s = 0) do: if (313) then r=r+r+r; Si= /3; else if (3|(s 1)) then: a:= a +r; r=r+r+r; S := (s - 1)/3; else: a:= a +r+r; roor+r+r; S := (s-2)/3; return (a). (a) Model the algorithm as a state machine whose states are triples of nonnegative integers (r; s; a). (b) b List the sequence of steps that appears in the execution of the algorithm for inputs x = 5 and y = 10. (c) ) Use the Invariant Method to prove that the algorithm is partially correctthat is, if s = 0, then a = xy. (d) Prove that the algorithm terminates after at most 1 + logz y executions of the body of the do statement