\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\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}
  \usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
  \usepackage{unicode-math}
  \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
}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\usepackage{hyperref}
\hypersetup{
            pdftitle={CSci 658: Software Language Engineering Mealy Machine Simulator Exercise},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\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

% set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother

\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}

\title{CSci 658: Software Language Engineering\\
Mealy Machine Simulator Exercise}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{21 January 2018}}

\begin{document}
\maketitle

\href{http://www.cs.olemiss.edu/~hcc}{H. Conrad Cunningham}\\
Professor of \href{https://www.cs.olemiss.edu}{Computer and Information
Science}\\
\href{http://www.olemiss.edu}{University of Mississippi}\\
211 Weir Hall\\
P.O. Box 1848\\
University, MS 38677\\
(662) 915-5358

\textbf{Advisory}: The HTML version of this document may require use of
a browser that supports the display of MathML. A good choice as of
January 2018 is a recent version of Firefox from Mozilla.

Copyright (C) 2016, 2017, 2018, H. Conrad Cunningham

TODO:

\begin{itemize}
\tightlist
\item
  Are the operations and their specifications reasonable for Haskell?
\item
  Is an \texttt{Either} the appropriate return in the various cases?
\item
  Should \texttt{getTransitionsFrom} return an \texttt{Either} for an
  invalid state?
\end{itemize}

\hypertarget{mealy-machine-simulator}{%
\section{Mealy Machine Simulator}\label{mealy-machine-simulator}}

\hypertarget{mealy-machine-definition}{%
\subsection{Mealy Machine Definition}\label{mealy-machine-definition}}

In this exercise, you are asked to design and implement Haskell modules
to represent Mealy Machines and to simulate their execution.

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, 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 textbook \emph{Formal Languages and Automata}, 6th
Ed., by Peter Linz (Jones \& Bartlett, 2017) 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 state 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.

\hypertarget{exercises}{%
\subsection{Exercises}\label{exercises}}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Design and implement a general representation for a Mealy Machine as a
  Haskell module implementing an abstract data type. It should hide the
  representation of the machine and should have, at least, the following
  public operations.

  \begin{itemize}
  \item
    \texttt{newMachine\ s} creates a new machine with initial (and
    current) state \texttt{s} and no transitions.

    Note: This assumes that the state, input, and output sets are
    exactly those added with the mutator operations below. An
    alternative would be to change this function to take the allowed
    state, input, and output sets.
  \item
    \texttt{addState\ m\ s} adds a new state \texttt{s} to machine
    \texttt{m} and returns an \texttt{Either} wrapping the modified
    machine or an error message.
  \item
    \texttt{addTransition\ m\ s1\ in\ out\ s2} adds a new transition to
    machine \texttt{m} and returns an \texttt{Either} wrapping the
    modified machine or an error message. From state \texttt{s1} with
    input \texttt{in} the modified machine outputs \texttt{out} and
    transitions to state \texttt{s2}.
  \item
    \texttt{addResets\ m} adds all reset transitions to machine
    \texttt{m} and returns the modified machine. From state \texttt{s1}
    on input \texttt{in} the modified machine outputs \texttt{out} and
    transitions to state \texttt{s2}. This operation makes the
    transition function a total function by adding any missing
    transitions from a state back to the initial state.
  \item
    \texttt{setCurrent\ m\ s} sets the current state of machine
    \texttt{m} to \texttt{s} and returns an \texttt{Either} wrapping the
    modified machine or an error message.
  \item
    \texttt{getCurrent\ m} returns the current state of machine
    \texttt{m}.
  \item
    \texttt{getStates\ m} returns a list of the elements of the state
    set of machine \texttt{m}.
  \item
    \texttt{getInputs\ m} returns a list of the input set of machine
    \texttt{m}.
  \item
    \texttt{getOutputs\ m} returns a list of the output set of machine
    \texttt{m}.
  \item
    \texttt{getTransitions\ m} returns a list of the transition set of
    machine \texttt{m}. Tuple \texttt{(s1,in,out,s2)} occurs in the
    returned list if and only if, from state \texttt{s1} with input
    \texttt{in}, the machine outputs \texttt{out} and moves to state
    \texttt{s2}.
  \item
    \texttt{getTransitionsFrom\ m\ s} returns an \texttt{Either}
    wrapping a list of the set of transitions enabled from state
    \texttt{s} of machine \texttt{m}or an error message.
  \end{itemize}
\item
  Given the above implementation for a Mealy Machine, design and
  implement a separate Haskell module that simulates the execution of a
  Mealy Machine. It should have, at least, the following new public
  operations.

  \begin{itemize}
  \item
    \texttt{move\ m\ in} moves machine \texttt{m} from the current state
    given input \texttt{in} and returns an \texttt{Either} wrapping a
    tuple \texttt{(m\textquotesingle{},out)} or an error message. The
    tuple gives the modified machine \texttt{m\textquotesingle{}} and
    the output \texttt{out}.
  \item
    \texttt{simulate\ m\ ins} simulates execution of machine \texttt{m}
    from its current state through a sequence of moves for the inputs in
    list \texttt{ins} and returns an \texttt{Either} wrapping a tuple
    \texttt{(m\textquotesingle{},outs)} or an error message. The tuple
    gives the modified machine \texttt{m\textquotesingle{}} after the
    sequence of moves and the output list \texttt{outs}.
  \end{itemize}
\item
  Implement a Haskell module that uses a different representation for
  the Mealy Machine. Make sure the simulator module still works
  correctly.
\end{enumerate}

\hypertarget{acknowledgements}{%
\subsection{Acknowledgements}\label{acknowledgements}}

In Spring 2017, I adapted this from a project I had assigned in the
Scala-based offering of CSci 555 Functional Programming in Spring 2016.
I edited the format slightly in Spring 2018.

I maintain these notes as text in Pandoc's dialect of Markdown using
embedded LaTeX markup for the mathematical formulas and then translate
the notes to HTML, PDF, and other forms as needed.

\hypertarget{concepts}{%
\subsection{Concepts}\label{concepts}}

TODO

\end{document}