CONISAR Proceeding 2015

Wilmington, North Carolina

2015 CONISAR Proceedings - Abstract Presentation

Utilizing Finite State Machines in the Classroom to Introduce Verified Software

Ronald Finkbine
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: 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.