NAME
FLAT  Formal Language & Automata Toolkit
Name Change Possibility
Future releases of this module may very well reflect a name change that is considered to me more normal for Perl modules. When this was originally written (2006) as a homework assignment, the original author was not very well versed in the idiomatic aspects of PERL
. Shortly after, a friendly fellow traveller rewrote it. Since then, this module has patiently sat on CPAN waiting for a use. Recently, this use has come in the form of a module for managing sequential consistency in Perl &
perl  Sub::Genius.
SYNOPSIS
FLAT.pm is the base class of all regular language objects. For more information, see other POD pages. It provides full support for the shuffle operator, which is useful for expressing the regular interleaving of regular languages.
DESCRIPTION
This module provides an interface for manipulating the formal language concept of Regular Expressions, which are used to describe Regular Languages, and their equivalent forms of Automata.
It's notable that this module supports, in addition to the traditional Regular Expression operators, the shuffle
operator (see [1]). This is expressed as an ampersand, &
. In addition to this, logical symbols may be multiple characters. This leads to some interesting applications.
While the module can do a lot, i.e.:
parse a regular expression (RE) (of the formal regular language variety)
convert a RE to a NFA (and similarly, a shuffle of two regular languages to a parallel NFA (PFA))
convert a PFA to a NFA (note, PFAs are equivalent to PetriNets (see [2], Graph::PetriNet)
convert a NFA to a DFA
convert a DFA to a minimal DFA
generate strings that may be accepted by a DFA
It is still missing some capabilities that one would expect:
generate equivalent REs from a NFA or DFA
provide targeted conversion of PFAs, NFAs, DFAs to their more explicit state forms; this is particularly interested to have in the case of the PFA.
provide targeted serialization of PREs (REs with a shuffle) using direct, explicit manuplation of the AST produced by the parser
provide other interesting graphbased manipulations that might prove useful, particular when applied to a graph that represents some form of a finite automata (FA)
In addition to the above deficiencies, application of this toolkit in interesting areas would naturally generate ideas for new and interesting capabilities.
Sequential Consistency and PREs
Valid strings accepted by the shuffle of one or more regular languages is necessarily sequentially consistent. This results from the conversions to a DFA that may be traversed inorder to discover valid string paths necessarily obeys the total ordering constraints of each constituent language of the two being shuffled; and the partial ordering that results among valid string accepted by both (see [2] for more on how PetriNets fit in).
USAGE
All regular language objects in FLAT implement the following methods. Specific regular language representations (regex, NFA, DFA) may implement additional methods that are outlined in the repsective POD pages.
Conversions Among Representations
 $lang>as_nfa
 $lang>as_dfa
 $lang>as_min_dfa
 $lang>as_regex

Returns an equivalent regular language to $lang in the desired representation. Does not modify $lang (even if $lang is already in the desired representation).
For more information on the specific algorithms used in these conversions, see the POD pages for a specific representation.
Closure Properties
 $lang1>union($lang2, $lang3, ... )
 $lang1>intersect($lang2, $lang3, ... )
 $lang1>concat($lang2, $lang3, ... )
 $lang1>symdiff($lang2, $lang3, ... )

Returns a regular language object that is the union, intersection, concatenation, or symmetric difference of $lang1 ... $langN, respectively. The return value will have the same representation (regex, NFA, or DFA) as $lang1.
 $lang1>difference($lang2)

Returns a regular language object that is the set difference of $lang1 and $lang2. Equivalent to
$lang1>intersect($lang2>complement)
The return value will have the same representation (regex, NFA, or DFA) as $lang1.
 $lang>kleene
 $lang>star

Returns a regular language object for the Kleene star of $lang. The return value will have the same representation (regex, NFA, or DFA) as $lang.
 $lang>complement

Returns a regular language object for the complement of $lang. The return value will have the same representation (regex, NFA, or DFA) as $lang.
 $lang>reverse

Returns a regular language object for the stringwise reversal of $lang. The return value will have the same representation (regex, NFA, or DFA) as $lang.
Decision Properties
 $lang>is_finite
 $lang>is_infinite

Returns a boolean value indicating whether $lang represents a finite/infinite language.
 $lang>is_empty

Returns a boolean value indicating whether $lang represents the empty language.
 $lang1>equals($lang2)

Returns a boolean value indicating whether $lang1 and $lang2 are representations of the same language.
 $lang1>is_subset_of($lang2)

Returns a boolean value indicating whether $lang1 is a subset of $lang2.
 $lang>contains($string)

Returns a boolean value indicating whether $string is in the language represented by $lang.
AUTHORS & ACKNOWLEDGEMENTS
FLAT is written by Mike Rosulek <mike at mikero dot com> and B. Estarde <estradb at gmail dot com>.
LICENSE
This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself.