NAME

PFA - A parallel finite automata base class

SYNOPSIS

use PFA;

DESCRIPTION

This module is implements a paralle finite automata, and the conversion of such to a non deterministic finite automata;

One key between PFA implementation an PFA & DFA is that the PFA may contain more than one start node since it may depict threads of concurrent execution. The main purpose of this module is to convert a PFA to an PFA.

Methods

new

Returns a new PFA object

load_file

Creates PFA from file

load_string

Creates PFA from string

jump_start

Returns an PFA with 1 start state, one final state, and a single transistion on the given symbol; if a symbol is not provided, epsilon is used.

find_tied

Determines the tied nodes in $self, and stores them in $self->{_TIED} for easy lookup. Use $self->is_tied(@testset) to determine if a set of nodes contains anything tied on lambda

get_tied

Determines if any tied nodes are contained in the provided node set

has_tied

Determines if all nodes in a tied set are contained in the provided node set

extract_tied

Extracts all tied nodes in a set and returns a flattened array

to_nfa

To NFA Stuff - convert PFA to NFA using subset construction technique

serialize_name

Creates a string based on the items in the array;

set_start

Sets start node, calls FA->add_node

get_start

Returns start nodes

set_active

Sets active node, calls FA->add_node

get_active

Returns active nodes

add_node

Adds a node label to the node array if it does not already exist (handles dups)

get_nodes

Returns the array of all nodes

add_transition

Adds a transition - adds node and symbol as well - unique nodes and symbols enforced by PFA->add_node and PFA->add_symbol

get_transition_on

Returns transition(s), as an array, for a specific node on a specific input symbol; This is not in FA.pm as it is PFA specific.

is_start

Checks to see if given node is in the start node array

set_epsilon

Sets epsilon symbol - not working with Perl special vars - $,@,%, etc

get_epsilon_symbol

Returns epsilon symbol

get_epsilon_transitions

Returns all epsilon transitions for a particular node; node must exist

delete_epsilon

Deletes epsilon symbol

set_lambda

Sets lambda symbol - not working with Perl special vars - $,@,%, etc

get_lambda_symbol

Returns lambda symbol

get_lambda_transitions

Returns all lambda transitions for a particular node; node must exist

delete_lambda

Deletes lambda symbol

is_node

Tests if given string is the name of a node

add_final

Adds a list of node lables to the final nodes array; handles dups, and ensures nodes are added to set of nodes

get_final

Returns the array of all final nodes

is_final

Checks to see if given node is in the final node array

clone

Returns a distinct clone of self

append_pfa

Concatenates start node of given PFA to the common final node of self; usage: my PFA->append_pfa($PFA1);

prepend_pfa

Concatenates start node of self to the common final node of the given PFA; usage: my PFA->prepend_pfa($PFA1);

or_pfa

Creates a common start node joined by an epsilon transition; usage: my PFA->or_pfa($PFA1);

interleave_pfa

Joins 2 PFAs using an interleave (concurrent process).

kleene

Wraps given PFA in Kleene Closure usage: my PFA->kleene();

pinch

Creates epsilon transitions from all final nodes to a common final node; . usage: my $PFA3 = PFA->pinch_pfa($PFA1); does nothing if there is only one final node

rename_nodes

Renames a single node; warns and changes nothing if name conflicts with another node

ensure_unique_nodes

Compares the names of the nodes in $self and the provided FA, and only renames a node (in $self) if a name collision is detected; if the disambiguation string causes a new collision, a random string is created using crypt() until there is no collision detected

Usage: $self->ensure_unique_nodes($PFA1,'string_to_disambiguate');

number_nodes

Numbers nodes 0-# of nodes; first appends node name with a random string to avoid conflicts

append_node_names

Appends node names with the specified suffix

prepend_node_names

Prepends node names with the specified prefix

rename_symbol

Renames symbol in pfa

info

Return string with info

serialize

Prints a valid string suitable for an input to stdout

AUTHOR

Brett D. Estrade - <estrabd AT mailcan DOT com>

CAVEATS

Currently, all nodes are stored as labels. There is also no integrity checking for consistency among the start, final, and set of all nodes.

BUGS

Not saying it is bug free, just saying I haven't hit any yet :)

AVAILABILITY

Anonymous CVS Checkout at http://www.brettsbsd.net/cgi-bin/viewcvs.cgi/

ACKNOWLEDGEMENTS

This suite of modules started off as a homework assignment for a compiler class I took for my MS in computer science at the University of Southern Mississippi.

COPYRIGHT

This code is released under the same terms as Perl.