NAME

FA - A finite automata base class

SYNOPSIS

use FA;

DESCRIPTION

This module is a base finite automata used by NFA and DFA to encompass common functions. It is probably of no use other than to organize the DFA and NFA modules.

Methods

set_start

Sets start state, calls FA->add_state

get_start

Returns start state name as string

is_start

Tests is string is the start state

add_state

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

get_states

Returns the array of all states

ensure_unique_states

Compares the names of the states in $self and the provided FA, and only renames a state (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_states($NFA1,'string_to_disambiguate');

number_states

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

append_state_names

Appends state names with the specified suffix

prepend_state_names

Prepends state names with the specified prefix

is_state

Tests if given string is the name of a state

add_final

Adds a list of state lables to the final states array; handles dups and ensures state is in set of states $self->{{STATES}

remove_final

Removes the given state from $self->{_FINAL_STATES}

get_final

Returns the array of all final states

is_final

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

add_symbol

Adds symbol to the symbol array; handles dups

is_symbol

Checks to see if given symbol is in the symbol array

get_symbols

Returns array of all symbols

get_transition

Returns hash of all transitions (symbols and next states) for given state

get_all_transitions

Returns hash of all transitions for all states and symbols

has_transition_on

Tests if given state has a transition on given symbol

has_transitions

Tests if given state has a transition on given symbol

delete_transition

Deletes transition given the state and the symbol

to_file

Dumps FA to file in the proper input file format

compliment

Returns compliment of 2 arrays - i.e., the items that they do not have in common; requires arrays be passed by reference; example: my @compliment = $self->compliment(\@set1,\@set2);

is_member

Tests if string is in given array

DESTROY

Called automatically when object is no longer needed

AUTHOR

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

CAVEATS

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

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.