CSci 658: Software Language Engineering
Mealy Machine Simulator Exercise

H. Conrad Cunningham

21 January 2018

H. Conrad Cunningham
Professor of Computer and Information Science
University of Mississippi
211 Weir Hall
P.O. Box 1848
University, MS 38677
(662) 915-5358

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:

Mealy Machine Simulator

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 Mealy Machine is a finite-state automaton whose output values are determined both by its current state and the current input. It is a deterministic finite state transducer such that, for each state and input, at most one transition is possible.

Appendix A of the textbook Formal Languages and Automata, 6th Ed., by Peter Linz (Jones & Bartlett, 2017) defines a Mealy Machine mathematically by a tuple

M=(Q,Σ,Γ,δ,θ,q0)M = (Q,\Sigma,\Gamma,\delta,\theta,q_{0})

where

QQ 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)
δ:Q×ΣQ\delta: Q \times \Sigma \longrightarrow Q is the transition function
θ:Q×ΣΓ\theta: Q \times \Sigma \longrightarrow \Gamma is the output function
q0q_{0} is the initial state of MM (an element of QQ)

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

δ:Q×ΣQ×Γ\delta: Q \times \Sigma \longrightarrow Q \times \Gamma

We often find it useful to picture a finite state machine as a 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.

Exercises

  1. 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.

  2. 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.

  3. Implement a Haskell module that uses a different representation for the Mealy Machine. Make sure the simulator module still works correctly.

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.

Concepts

TODO