  An introductory formal languages course exposes advanced undergraduate and
early graduate students to automata theory, grammars, constructive proofs,
computability, and decidability. Programming 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 since
students are asked to design and prove correct machines and grammars without
being able to experiment nor get immediate feedback, which is essential in a
learning context. This article puts forth the thesis that the theory of
computation ought to be taught using tools for actually building computations.
It describes the implementation and the classroom use of a library, FSM,
designed to provide students with the opportunity to experiment and test their
designs using state machines, grammars, and regular expressions. Students are
able to perform random testing 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.
