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 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.