Quick Start For The Impatient

From The Perl Formal Language Toolkit

We recently added "one liner" support via the fash (finite automata shell) utility that is installed into Config::$Config{installbin}.

Internally, fash provides an simpler interface to commands at the commandline using the "perl -MFLAT::CMD -e cmd" idiom. Below is a summary, which can be seen in full using fash.

The example below generates a PNG picture of the minimal DFA (minus the sink states) for a regular expression:

 %fash dfa2gv "abc+def"' | dot -Tpng > dfa.png

The qiv program is nice and light weight enough to view these images. For larger images, you'll need something like GIMP.

Another example shows the output from one of the "2digraph" commands

 %fash dfa2digraph abc+def

The output created looks like:

 6           // number of nodes
 0 (2) 1 2   // node# (#neighbors) neighbor1 neighbor2...neighborN
 1 (1) 3     // ..
 2 (1) 4     // ..
 3 (1) 5     // ..
 4 (1) 5     // ..
 5 (0)       // ..

Alternatively, the undirected graph generated from the command

 %fash dfa2undirected abc+def

produces:

 6
 0 (2) 1 2
 1 (2) 0 3
 2 (2) 0 4
 3 (2) 1 5
 4 (2) 2 5
 5 (2) 3 4

Testing strings agains a regular expression is accomplished via the "test" command:

 %fash test 'a(b+c)' 'ab' 'ac' 'ad'
 (+): ab
 (+): ac
 (-): ad

This command also takes in piped STDIN; the first line is take as the regular expression, and everything after that is tested against it:

 %fash -b test < test.dat
 (+): a
 (+): ab
 (+): ac
 (-): ad
 (-): aa
 (+): abbbcccbcbcbcbcbc
 (+): abc
 (+): accbbccbbcc

Where "test.dat" looks like:

 a(b+c)* 
 a
 ab
 ac
 ad
 aa
 abbbcccbcbcbcbcbc
 abc
 accbbccbbcc

Strings may be generated using fash:

%fash somestrings abc+def
abc+def  # the supplied regex is printed first
abc
def

And in conjuction with the fash test action (provides a quick sanity check):

%fash somestrings "a&b&c" | fash -b test
(+): cab
(+): cba
(+): bac
(+): bca
(+): abc
(+): acb

Introduction

The Perl Formal Language Toolkit ( FLaT ), is a set of compatible Perl modules used for investigating regular expressions and finite automata. The projects goal is twofold; to create a tool kit, which:

1. may be used to create Perl utilities and applications that may utilize finite state machines and the ability to convert between machines and regular expressions;
2. may be used for formal and informal students of theoretical computer science to learn, explore, and build their knowledge base;

It started out as a way to learn finite automata, the Latin of Computer Science (as I like to call it). From there, it has turned into a hobby that I personally use to do stupid regular expression tricks. It is not built for speed, but for implementing the proper theory behind all of this automata and formal language mess. As the basic fundamental features of this toolkit is built up, more and more things are possible. For example, more powerful machines such as push down automata or Turing Machines could be implemented. Most importanly, however, it can be used for budding computer science students as an augmentation to their formal education.

At some point, this toolkit will yield a useful application, but for now I am happy using it to explore particular topics that I find interesting. These topics as related to this tool kit are: