\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage{hyperref}
\hypersetup{unicode=true,
            pdftitle={CSci 555-1: Functional Programming Spring 2016},
            pdfauthor={Assignment \#3: Mealy Machine Simulator Revised Deadline Friday, 22 April, 11:59 p.m. (Five extra points if completed by original deadline of 19 April)},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi
\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}

\title{CSci 555-1: Functional Programming\\
Spring 2016}
\author{Assignment \#3: Mealy Machine Simulator\\
Revised Deadline Friday, 22 April, 11:59 p.m.\\
(Five extra points if completed by original deadline of 19 April)}
\date{}

\begin{document}
\maketitle

Note: This document will only display correctly in a browser that
supports MathML.

\subsection{Introduction}\label{introduction}

In this assignment, you are to design and implement an abstract data
type to simulate a Mealy Machine. This kind of machine is a useful
abstraction for simple controllers that listen for input events and
respond by generating output events. For example in an automobile
application, the input might be an event such as ``fuel level low'' and
the output might be command to ``display low-fuel warning message''.

In the theory of computation (e.g., the general topic of the UM course
CSCI 311, Models of Computation), a \emph{Mealy Machine} is a
finite-state automaton whose output values are determined both by its
current state and the current input. It is a \emph{deterministic finite
state transducer} such that, for each state and input, at most one
transition is possible.

Appendix A of the current CSci 311 textbook (Peter Linz, \emph{Formal
Languages and Automata}, 5th Ed., Jones \& Bartlett, 2012) defines a
Mealy Machine mathematically by a tuple

\begin{quote}
\(M = (Q,\Sigma,\Gamma,\delta,\theta,q_{0})\)
\end{quote}

where

\begin{quote}
\(Q\) is a finite set of internal states\\
\(\Sigma\) is the input alphabet (a finite set of values)\\
\(\Gamma\) is the output alphabet (a finite set of values)\\
\(\delta: Q \times \Sigma \longrightarrow Q\) is the transition
function\\
\(\theta: Q \times \Sigma \longrightarrow \Gamma\) is the output
function\\
\(q_{0}\) is the initial state of \(M\) (an element of \(Q\))
\end{quote}

In an alternative formulation, the transition and output functions can
be combined into a single function:

\begin{quote}
\(\delta: Q \times \Sigma \longrightarrow Q \times \Gamma\)
\end{quote}

We often find it useful to picture a finite machine as a
\emph{transition graph} where the states are mapped to vertices and the
transition function represented by directed edges between vertices
labelled with the input and output symbols.

\subsection{Tasks}\label{tasks}

Design and implement a Mealy Machine simulator as an immutable Scala
``module'' using functional programming techniques.

You may, but are not required to, use the doubly labelled Digraph
abstract data type (presented in class) internally to represent the
transition graph.

Define an appropriate interface to the module. The Mealy Machine
abstract data type should have, at least, public operations to

\begin{itemize}
\item
  create a new machine (perhaps one with no states and no transitions)
\item
  add a new state to the machine
\item
  add a new transition to the machine
\item
  add all reset transitions (that is, make the transition function a
  total function by adding any missing transitions from a state back to
  the initial state)
\item
  set the ``initial'' state of the machine
\item
  get the current state of the machine
\item
  get a collection of all states of the machine
\item
  get a collection of all inputs enabled for a given state
\item
  move the machine forward one step given an input; the machine should
  generate the appropriate output and enable the next move from the
  destination state of this move (Note that, in a purely functional
  program, the ``move'' function probably needs to return two items--the
  next state and the output from the current move.)
\item
  do other needed tasks (if any) to complete the abstraction or to make
  your implementation work conveniently with Scala
\end{itemize}

Define a function (either as a part of the abstract data type or that
uses it) to execute the machine on a sequence of inputs, returning the
corresponding sequence of outputs and enabling the machine to be
continued with another sequence if needed.

Alternatively, you might want to split the above into two parts--a
builder abstract data type that enables a machine to be defined and a
separate abstract data type that executes a machine.

Remember, your design and implementation should avoid mutable state and
imperative Scala code.

Design appropriate tests for your functions and test them thoroughly.

Document your program appropriately.

Submit the source code and documentation for your program and test
driver, any needed instructions on how to run the program, and
appropriate test output to Blackboard. Be sure to identify yourself in
the materials turned in.

\end{document}