B. Estrade > FLAT-0.9.1 > FLAT::PFA



Annotate this POD

View/Report Bugs


FLAT::PFA - Parallel finite automata


A FLAT::PFA object is a finite automata whose transitions are labeled either with characters, the empty string (epsilon), or a concurrent line of execution (lambda). It essentially models two FSA in a non-deterministic way such that a string is valid it puts the FSA of the shuffled languages both into a final, or accepting, state. A PFA is an NFA, and as such exactly describes a regular language.

A PFA contains nodes and states. A state is made up of whatever nodes happen to be active. There are two transition functions, nodal transitions and state transitions. When a PFA is converted into a NFA, there is no longer a need for nodes or nodal transitions, so they go are eliminated. PFA model state spaces much more compactly than NFA, and an N state PFA may represent 2**N non-deterministic states. This also means that a PFA may represent up to 2^(2^N) deterministic states.


(not implemented yet)

In addition to implementing the interface specified in FLAT and FLAT::NFA, FLAT::PFA objects provide the following PFA-specific methods:


Shuffle construct for building a PFA out of a PRE (i.e., a regular expression with the shuffle operator)


Converts a PFA to an NFA by enumerating all states; similar to the Subset Construction Algorithm, it does not implement e-closure. Instead it treats epsilon transitions normally, and joins any states resulting from a lambda (concurrent) transition using an epsilon transition.


FLAT is written by Mike Rosulek <mike at mikero dot com> and Brett Estrade <estradb at gmail dot com>.

The initial version (FLAT::Legacy) by Brett Estrade was work towards an MS thesis at the University of Southern Mississippi.

Please visit the Wiki at http://www.0x743.com/flat


This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

syntax highlighting: