NAME

NFA - A non deterministic finite automata base class

SYNOPSIS

use NFA;

DESCRIPTION

This module implements a non deterministic finite automata, including support for epsilon transitions and conversion to a deterministic finite automata.

Methods

new

Returns a new FA object

jump_start

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

load_file

Creates NFA from file

load_string

Creates NFA from string

clone

Returns a distinct clone of self

append_nfa

Concatenates start state of given NFA to the common final state of self; usage: my NFA->append_nfa($NFA1);

prepend_nfa

Concatenates start state of self to the common final state of the given NFA; usage: my NFA->prepend_nfa($NFA1);

or_nfa

Creates a common start state joined by an epsilon transition; usage: my NFA->or_nfa($NFA1);

kleene

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

pinch

Creates epsilon transitions from all final states to a common final state; . usage: my $NFA3 = NFA->pinch_nfa($NFA1); does nothing if there is only one final state

reverse

Reverses an NFA

rename_states

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

rename_symbol

Renames symbol in nfa

add_transition

Adds a transition - adds state and symbol as well - unique states and symbols enforced by NFA->add_state and NFA->add_symbol; since this is an NFA, transitions on $symbol from $state may be added to multiple destinations

get_transition_on

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

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 state; state must exist

delete_epsilon

Deletes epsilon symbol

to_dfa

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

move

Get all transition states for the specific symbol **candidate for anonymous sub in NFA->to_dfa()

epsilon_closure

Peform e-closure - get all the states that the provided subset of states transitions to on epsilon (empty string) **candidate for anonymous sub in NFA->to_dfa()

info

Return string with info

serialize

Prints a valid string suitable for an input to stdout

generate_random

Generates random DFA; not implemented

generate_from_strings

Will be used to create an NFA that will accept @THIS, but not @THAT

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.