Utilizing Finite State Machines in the Classroom to
Introduce Verified Software
Indiana University Southeasty
A finite state machine (FSM) is a graphical model that displays the
computational behavior of a system by determining the acceptance (yes or no)
of an input sequence. These models can be rendered in standard language source
programs as regular source code or can be included using an FSM tool developed by
the author. The FSM concept has traditionally been introduced to students in a
course on computability but often not included in software development courses.
The author has been using a sequence of FSM-based assignments in courses in
Programming Languages, Software Engineering and Operating Systems.
These assignments include the following:
Simple integers base 10
Integers base 2, 8, 10, 16
Floats including scientific notation
Simple Vending machine
This paper shows the Chomsky Hierarchy and its equivalence to the Deterministic Finite Automaton (DFA), a subset of the FSM concept. A single sequence of input (and no data storage) is equivalent to the class of regular grammars (Chomsky’s Type-3). Components of this computational power solve a very limited set of problems as language acceptors.
Adding even more storage moves the computational complexity into Type-1 on the Chomsky scale and now we have a symbol table and can write compilers, insisting the variables used in out input data stream have been declared and are of the correct type.
This paper/presentation/discussion shows an attempt to move the FSM and Chomsky Hierarchy discussions from the computation complexity course into the programming languages and software engineering courses in the undergraduate curriculum.
Recommended Citation: Finkbine, R., (2015). Utilizing Finite State Machines in the Classroom to
Introduce Verified Software. The Proceedings of the Conference on Information
Systems Applied Research, v.8 n.3697, Wilmington, North Carolina.