\problem\pts{20}

This problem involves two labeled state machines,
called $\ms{Bag}$ and $\ms{Stack}$, each of which keeps track of a
collection of integers. 
A ``client'' can interact with each using requests and responses.
Both support the same kinds of operations: $\ms{insert}$ and
$\ms{get}$, though the operations behave a little differently in the
two machines.

$\ms{Bag}$ maintains a ``bag'' of integers, which is like a set of
integers except it allows repeats. 
Written out in detail: 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\= \kill
$\ms{Bag}$ Labeled State Machine: \\
\\
$Q$: 
\> $B$, a bag of integers \\
\> $\ms{req}$, either $\ms{insert}(x)$, $\ms{get}$, or $\ms{null}$ \\
\> $\ms{resp}$, either $\ms{OK}$, an integer, $\ms{error}$, or
$\ms{null}$ \\
\\
$Q_0$: 
\> $B$ is the empty bag, $\ms{req} = \ms{resp} = \ms{null}$ \\
\\
$L$:
\> Input: $\ms{insert}(x)$, $\ms{get}$ \\
\> Internal: $\ms{perform}(\ms{insert}(x))$,$\ms{perform}(\ms{get})$ \\
\> Output: $\ms{respond}(r)}$\\
\\
$\delta$:
\> $\ms{insert}(x)$:\\ 
\> \> Can occur:  Anytime \\ 
\> \> Effect: if $\ms{req} = \ms{null}$ then $\ms{req} := \ms{insert}(x)$ \\
\> $\ms{get}$: \\
\> \> Can occur:  Anytime \\
\> \> Effect: if $\ms{req} = \ms{null}$ then $\ms{req} := \ms{get}$ \\
\\
\> $\ms{perform}(\ms{insert})$: \\
\> \> Can occur if: $\ms{req} = \ms{insert}(x)$ \\
\> \> Effect: add $x$ to $B$; $\ms{resp} := $\ms{OK} \\
\> $\ms{perform}(\ms{get})$: \\
\> \> Can occur if: $\ms{req} = \ms{get}$ \\
\> \> Effect: \\
\> \> \> if $B$ is nonempty then \\
\> \> \> \> choose any element $x$ in $B$ and remove one copy from $B$; \\
\> \> \> \> $\ms{resp} := x$ \\
\> \> \> else $\ms{resp} := \ms{error}$ \\ 
\\
\> $\ms{respond}(r)$: \\
\> \> Can occur if: $\ms{resp} = r$, $r \not= \ms{null}$ \\
\> \> Effect: $\ms{req} := \ms{null}$; $\ms{resp}$ := \ms{null}$
\end{tabbing}

\nextproblem
The other machine, $\ms{Stack}$, differs from $\ms{Bag}$ only in its
state and the $\ms{perform}$ transitions:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\= \kill
$\ms{Stack}$ Labeled State Machine: \\
\\
$Q$: 
\> $S$, a sequence of integers \\
\> $\ms{req}$, $\ms{resp}$, as for $\ms{Bag}$ \\
\\
$Q_0$:
\> $S$ is the empty sequence, $\ms{req} = \ms{resp} = \ms{null}$ \\
\\
$\delta$:\\
\> $\ms{perform}(\ms{insert})$: \\
\> \> Can occur if: $\ms{req} = \ms{insert}(x)$ \\
\> \> Effect: $S = x S$, where $x S$ is the concatenation of $x$ and $S$; \\
\> \> \>  $\ms{resp} := $\ms{OK} \\
\> $\ms{perform}(\ms{get})$: \\
\> \> Can occur if: $\ms{req} = \ms{get}$ \\
\> \> Effect: \\
\> \> \> if $S$ is nonempty then \\
\> \> \> \> $\ms{resp} := \ms{head}(S)$ (the first element of $S$); \\
\> \> \> \> $S := \ms{tail}(S)$ (all but the first element);
\> \> \> else $\ms{resp} := \ms{error}$ 
\end{tabbing}

\problempart{\bf (10 points)}
Does $\ms{Stack}$ implement $\ms{Bag}$ ?
If your answer is yes, then give an abstraction
relation.  If it is no, then give an example of a
trace of $\ms{Stack}$ that is not a trace of $\ms{Bag}$.

\problempart{\bf (10 points)}

Does $\ms{Bag}$ implement $\ms{Stack}$ ?
If so, give an abstraction relation.  If not, give a 
trace of $\ms{Bag}$ that is not a trace of $\ms{Stack}$.












