2015 CONISAR Proceedings  Abstract Presentation
Utilizing Finite State Machines in the Classroom to
Introduce Verified Software
Ronald Finkbine
Indiana University Southeasty
Abstract
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 FSMbased assignments in courses in
Programming Languages, Software Engineering and Operating Systems.
These assignments include the following:
 A*b

Ab*c

Identifier

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 Type3). Components of this computational power solve a very limited set of problems as language acceptors.
Adding even more storage moves the computational complexity into Type1 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.