File:Tfpie2014 submission 14.pdf

An introductory formal languages course exposes students to automata theory, grammars, constructive proofs, computability, and decidability. This exposure usually comes late in the undergraduate curriculum or early in the graduate curriculum. In either setting, programming-oriented students find these topics to be challenging or, in many cases, overwhelming and on the fringe of Computer Science. The existence of this perception is not completely absurd, because rarely do formal languages courses, unlike programming courses, offer the sufficient software infrastructure for students to experiment with their ideas and designs. This article describes a library, FSM, designed to provide students with the opportunity to experiment and test their designs using finite-state machines, regular expressions, regular grammars, pushdown automata, context-free grammars, Turing machines, and context-sensitive grammars. Students are able to implement and test machines and grammars of their own design before proceeding with a formal proof of correctness. That is, students can test their designs much like they do in a programming course. In addition, the library easily allows students to implement the algorithms they develop as part of the constructive proofs they write. Providing students with this ability ought to be a new trend in the formal languages classroom.