\documentstyle[epsf]{article}

\input{./handout}

\begin{document}

\homework{4}{20 September 1995}{Sequences, Induction; State Machines}{}

\problem{1}

Chapter 7 of SEM: 7.1, 7.2, 7.3

\problem{2}

Chapter 8 of SEM: 8.2, 8.3, 8.7, 8.8

\problem{3}

A certain simple answering machine (not unlike the one on my desk) has
two buttons (``play'' and ``save'') 
and (of course) can receive messages.  If someone plays the
messages and doesn't save them, they are erased/overwritten when the
next incoming message is received.  The answering machine only holds a
specified 
number of messages; when it reaches full capacity, it refuses to accept
new messages.  The answering machine can be modeled by the state
machine {\bf AnsMachine} whose state transition diagram is below.

\centerline{\epsfbox{ans-machine.ps}}
\newpage
\begin{enumerate}
\item Give a $4$-tuple description for this state machine.
\item Give three execution fragments of {\bf AnsMachine}, at least one
  of which is not an execution.  
\item Give both a finite and an infinite execution of {\bf AnsMachine}.
\item For each of the following, indicate whether or not it is an
  event-based trace of {\bf AnsMachine}.
  \begin{enumerate}
  \item play save msg msg play
  \item msg msg msg play save msg msg msg
  \item msg play save msg msg play msg msg msg
  \end{enumerate}
\item Give two examples of state-based traces of {\bf AnsMachine}. 
\item Give two sequences of states which are {\em not} state-based
  traces of {\bf AnsMachine}.
\item What are the reachable states of this machine?
\item Is {\bf AnsMachine}'s event-based behavior finite or infinite?
\item Can a state machine $M=\langle S,I,A,\delta\rangle$ with an
  infinite trace have an infinite behavior?  Give an example or explain
  why not. 
\end{enumerate}

\end{document}