[Pl-seminar] Semantics Seminar Schedule
wand at ccs.neu.edu
Fri Aug 4 00:05:02 EDT 2006
*NOTE NON-STANDARD DAY*
NU Programming Languages Seminar
Room 366 WVH (http://www.ccs.neu.edu/home/wand/directions.html)
Experimenting with Formal Languages using Forlan
Kansas State University
Since the 1930s, the subject of formal language theory, also known as
automata theory, has been developed by computer scientists, linguists
and mathematicians. Because of its many applications to computer
science, most CS programs offer both undergraduate and graduate
courses in this subject. Many of the results of formal language
theory are proved constructively, using algorithms that are useful in
practice. In typical courses on formal language theory, students
apply these algorithms to toy examples by hand, and learn how they are
used in applications. But they are not able to experiment with them
on a larger scale.
Over the past several years, I have been designing and developing a
computer toolset, called Forlan, for experimenting with formal
languages. Forlan is implemented in the functional programming
language Standard ML, a language whose notation and concepts are
similar to those of mathematics. Forlan is used interactively; in
fact, a Forlan session is simply a Standard ML session in which the
Forlan modules are pre-loaded. Users are able to extend Forlan by
defining ML functions.
In Forlan, the usual objects of formal language theory -- automata,
regular expressions, grammars, labeled paths, parse trees, etc. -- are
defined as abstract types, and have concrete syntax. The standard
algorithms of formal language theory are implemented in Forlan,
including conversions between different kinds of automata and
grammars, the usual operations on automata and grammars, equivalence
testing and minimization of DFAs, etc.
In my talk, I will give a brief introduction to formal language
theory, and will then give an extended example of how one can
experiment with formal languages using Forlan.
Forlan is an open source project; it may be downloaded from
More information concerning Forlan, including a draft (open source)
textbook on formal language theory, can be found on this WWW site.
More information about the pl-seminar