\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
  english,
]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\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{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\hypersetup{
  pdftitle={CSci 555: Functional Programming Mealy Machine Simulator Project},
  pdfauthor={H. Conrad Cunningham},
  pdfborder={0 0 0},
  breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-2}
% 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}
\ifnum 0\ifxetex 1\fi=0 % if pdftex or luatex
  \usepackage[shorthands=off,main=english]{babel}
\else % if xetex
  % load polyglossia as late as possible as it *could* call bidi if RTL lang (e.g. Hebrew or Arabic)
  \usepackage{polyglossia}
  \setmainlanguage[]{english}
\fi

\title{CSci 555: Functional Programming\\
Mealy Machine Simulator Project}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{IN WORK 6 March 2019}}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
Copyright (C) 2016, 2017, 2018, 2019,
\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)

\textbf{Browser Advisory:} The HTML version of this textbook requires a
browser that supports the display of MathML. A good choice as of March
2019 is a recent version of Firefox from Mozilla.

TODO:

\begin{itemize}
\tightlist
\item
  Complete description for use with Scala (was Haskell)
\item
  Are the operations and their specifications reasonable?
\item
  Is an \VERB|\NormalTok{Either}| the appropriate return in the various
  cases?
\item
  Should \VERB|\NormalTok{getTransitionsFrom}| return an
  \VERB|\NormalTok{Either}| for an invalid state?
\end{itemize}

\newpage

\hypertarget{mealy-machine-simulator-project}{%
\subsection{Mealy Machine Simulator
Project}\label{mealy-machine-simulator-project}}

In this project, you are asked to design and implement a Scala program
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
\emph{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 Linz textbook {[}Linz 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}}

TODO: Decide whether these functions are appropriate for the intended
Scala structure. In particular should these be methods on a class rather
than just functions. Should the constructor be a class constructor? etc.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Specify, design, and implement a general representation for a Mealy
  Machine as a set of Scala definitions 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
    \VERB|\FunctionTok{newMachine}\NormalTok{(s)}| creates a new machine
    with initial (and current) state \VERB|\NormalTok{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
    \VERB|\FunctionTok{addState}\NormalTok{(m,s)}| adds a new state
    \VERB|\NormalTok{s}| to machine \VERB|\NormalTok{m}| and returns an
    \VERB|\NormalTok{Either}| wrapping the modified machine or an error
    message.
  \item
    \VERB|\FunctionTok{addTransition}\NormalTok{(m,s1,in,out,s2)}| adds
    a new transition to machine \VERB|\NormalTok{m}| and returns an
    \VERB|\NormalTok{Either}| wrapping the modified machine or an error
    message. From state \VERB|\NormalTok{s1}| with input
    \VERB|\NormalTok{in}| the modified machine outputs
    \VERB|\NormalTok{out}| and transitions to state
    \VERB|\NormalTok{s2}|.
  \item
    \VERB|\FunctionTok{addResets}\NormalTok{(m)}| adds all reset
    transitions to machine \VERB|\NormalTok{m}| and returns the modified
    machine. From state \VERB|\NormalTok{s1}| on input
    \VERB|\NormalTok{in}| the modified machine outputs
    \VERB|\NormalTok{out}| and transitions to state
    \VERB|\NormalTok{s2}|. This operation makes the transition function
    a total function by adding any missing transitions from a state back
    to the initial state.
  \item
    \VERB|\FunctionTok{setCurrent}\NormalTok{(m,s)}| sets the current
    state of machine \VERB|\NormalTok{m}| to \VERB|\NormalTok{s}| and
    returns an \VERB|\NormalTok{Either}| wrapping the modified machine
    or an error message.
  \item
    \VERB|\FunctionTok{getCurrent}\NormalTok{(m)}| returns the current
    state of machine \VERB|\NormalTok{m}|.
  \item
    \VERB|\FunctionTok{getStates}\NormalTok{(m)}| returns a list of the
    elements of the state set of machine \VERB|\NormalTok{m}|.
  \item
    \VERB|\FunctionTok{getInputs}\NormalTok{(m)}| returns a list of the
    input set of machine \VERB|\NormalTok{m}|.
  \item
    \VERB|\FunctionTok{getOutputs}\NormalTok{(m)}| returns a list of the
    output set of machine \VERB|\NormalTok{m}|.
  \item
    \VERB|\FunctionTok{getTransitions}\NormalTok{(m)}| returns a list of
    the transition set of machine \VERB|\NormalTok{m}|. Tuple
    \VERB|\NormalTok{(s1,in,out,s2)}| occurs in the returned list if and
    only if, from state \VERB|\NormalTok{s1}| with input
    \VERB|\NormalTok{in}|, the machine outputs \VERB|\NormalTok{out}|
    and moves to state \VERB|\NormalTok{s2}|.
  \item
    \VERB|\FunctionTok{getTransitionsFrom}\NormalTok{(m,s)}| returns an
    \VERB|\NormalTok{Either}| wrapping a list of the set of transitions
    enabled from state \VERB|\NormalTok{s}| of machine
    \VERB|\NormalTok{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
    \VERB|\FunctionTok{move}\NormalTok{(m,in)}| moves machine
    \VERB|\NormalTok{m}| from the current state given input
    \VERB|\NormalTok{in}| and returns an \VERB|\NormalTok{Either}|
    wrapping a tuple \VERB|\NormalTok{(mm,out)}| or an error message.
    The tuple gives the modified machine \VERB|\NormalTok{mm}| and the
    output \VERB|\NormalTok{out}|.
  \item
    \VERB|\FunctionTok{simulate}\NormalTok{(m,}\FunctionTok{ins}\NormalTok{(}|
    simulates execution of machine \VERB|\NormalTok{m}| from its current
    state through a sequence of moves for the inputs in list
    \VERB|\NormalTok{ins}| and returns an \VERB|\NormalTok{Either}|
    wrapping a tuple \VERB|\NormalTok{(mm,outs)}| or an error message.
    The tuple gives the modified machine \VERB|\NormalTok{mm}| after the
    sequence of moves and the output list \VERB|\NormalTok{outs}|.
  \end{itemize}

  Note: It is possible to use a Labelled Digraph ADT module in the
  implementation of the Mealy Machine.
\item
  Implement a Scala abstract data type 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}}

I created the original version of this project in Spring 2016 as a
programming exercise in the first Scala-based offering of CSci 555,
Functional Programming. I adapted and revised this project for possible
use in the Haskell-based CSci 556 course in Spring 2017 but did not
assign it. In 2018, I revised the project description and merged it into
new Chapter 23, Data Abstraction Revisited, in the textbook
\emph{Exploring Languages with Interpreters and Functional Programming}.

In Spring 2019, I separated the Mealy Machine Simulator Project back
into a separate document and modified it for use in a Scala-based
course.

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

\hypertarget{references}{%
\subsection{References}\label{references}}

\begin{description}
\tightlist
\item[{[}Linz 2017{]}:]
Peter Linz. \emph{Formal Languages and Automata}, 6th Edition, Jones \&
Bartlett, 2017.
\end{description}

\hypertarget{terms-and-concepts}{%
\subsection{Terms and Concepts}\label{terms-and-concepts}}

Mealy Machine, simulator, finite-state automaton (machine),
deterministic finite state transducer, state, transition, transition
graph.

\end{document}