Experimenting with formal languages using forlan

ABSTRACT

We give an introduction to the Forlan formal language theory toolset, which was designed to facilitate sophisticated experimentation with formal languages. Forlan is embedded in the functional programming language Standard ML, a language whose notation and concepts are similar to those of mathematics. It is strongly typed and interactive, properties that help make experimentation robust, simple and enjoyable. We give an extended example of the kind of experimentation that Forlan makes possible. It involves the use of closure properties/algorithms for regular languages/finite automata and a "difference" function on strings of zeros and ones.

REFERENCES

• 1: A. W. Appel and D. B. MacQueen. Standard ML of New Jersey. In Programming Language Implementation and Logic Programming, volume 528 of Lecture Notes in Computer Science, pages 1--26. Springer-Verlag, 1991.
• 2: Jon Barwise , John Etchemendy, Turing's World 3.0: An Introduction to Computability Theory, University of Chicago Press, Chicago, IL, 1993
• 3: Susan H. Rodger , Anna O. Bilska , Kenneth H. Leider , Magdalena Procopiuc , Octavian Procopiuc , Jason R. Salemme , Edwin Tsang, A collection of tools for making automata theory and formal languages come alive, Proceedings of the twenty-eighth SIGCSE technical symposium on Computer science education, p.15-19, February 27-March 01, 1997, San Jose, California, United States
• 4: Ted Hung , Susan H. Rodger, Increasing visualization and interaction in the automata theory course, Proceedings of the thirty-first SIGCSE technical symposium on Computer science education, p.6-10, March 07-12, 2000, Austin, Texas, United States
• 5: H. Leiß. The Automata Library. http://www.cis.uni-muenchen.de/leiss/sml-automata.html, 2000.
• 6: Sylvain Lombardy , Yann Régis-Gianas , Jacques Sakarovitch, Introducing VAUCANSON, Theoretical Computer Science, v.328 n.1-2, p.77-96, 29 November 2004 [doi>10.1016/j.tcs.2004.07.007]
• 7: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 8: Darrell Raymond , Derick Wood, Grail: a C++ library for automata and expressions, Journal of Symbolic Computation, v.17 n.4, p.341-350, April 1994 [doi>10.1006/jsco.1994.1023]
• 9: Matthew B. Robinson , Jason A. Hamshar , Jorge E. Novillo , Andrew T. Duchowski, A Java-based tool for reasoning about models of computation through simulating finite automata and Turing machines, The proceedings of the thirtieth SIGCSE technical symposium on Computer science education, p.105-109, March 24-28, 1999, New Orleans, Louisiana, United States
• 10: Susan H. Rodger, JFLAP: An Interactive Formal Languages and Automata Package, Jones and Bartlett Publishers, Inc., 2006
• 11: J. Saraiva. HaLeX: A Haskell library to model, manipulate and animate regular languages. In ACM Workshop on Functional and Declarative Programming in Education (FDPE/PLI'02), Pittsburgh, October 2002.
• 12: A. Stoughton. Experimenting with formal languages. In Thirty-sixth ACM SIGCSE Technical Symposium on Computer Science Education, page 566. ACM Press, 2005.
• 13: A. Stoughton. Formal Language Theory: Integrating Experimentation and Proof. http://people.cis.ksu.edu/~stough/forlan/, 2008.
• 14: K. Sutner. Implementing finite state machines. In N. Dean and G. E. Shannon, editors, Computational Support for Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 15, pages 347--363. American Mathematical Society, 1992.
• 15: S. Yu. Grail+: A symbolic computation environment for finite-state machines, regular expressions, and finite languages. http://www.csd.uwo.ca/Research/grail/, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

General Terms:
Algorithms, Experimentation, Languages, Theory

Keywords:
pedagogy, standard ml, toolset