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

Download:
FLAT-0.9.1.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Source  

NAME ^

FLAT::PFA - Parallel finite automata

SYNOPSIS ^

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.

USAGE ^

(not implemented yet)

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

$pfa->shuffle

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

$pfa->as_nfa

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.

AUTHORS & ACKNOWLEDGEMENTS ^

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

LICENSE ^

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

syntax highlighting: