NAME

DFA - A determinisitic finite automata base class

SYNOPSIS

use DFA;

DESCRIPTION

This module is implements a deterministic finite automata, including the testing of strings accepted by the DFA.

Methods

new

Returns a new FA object

jump_start

Returns an DFA with 1 start state, one final state, and a single transistion on the given symbol; if a symbol is not provided, only a single state that is both the start and end state is returned

load_file

Load DFA from file

load_string

Load DFA from string

clone

Returns a distinct clone of self

to_nfa

Returns an NFA; everything is copied exactly, but it is of class NFA

minimize

Minimizes number of states and transitions required to accept the regular language described by original $self; returns an array of the states removed

delete_state

Deletes state and all references to it...if the start start or only final state is deleted, a loud warning, messages will be issued; accepts an arbitrarily long list of states to delete, so you could do $dfa->delete_state(@states) or $dfa->delete_state($state);

rename_states

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

rename_symbol

Renames symbol in dfa

add_transition

Adds transition - note, one state per char...no subsets, that is what NFA is for :)

get_transition_on

Get transitions on input symbol from specified state; this is not in FA.pm as it is DFA specific.

reverse_dfa

Will return a DFA object that is the reverse of the current one.

to_gdl

Outputs a Graph Description Language (GDL) file that can be visualized using the program aiSee http://www.aisee.com/gdl/nutshell/intro.htm

info

Diagnostics, transition information

serialize

Prints a valid string suitable for an input to stdout

is_valid

Gives true (1) or false (0) as to if a string is valid

get_last_state

Returns accepting state, undef if string is not valid

get_path

Returns path taken

generate_random

Generates random DFA; not implemented

pump_strings

Generates accepted strings based on string length closures will not be repeated, but will be denoted with '*'; not implemented.

init_string_pump

Used to initiate iterative string pumping;

pump_next

Used to get next pumped string when being used iteratively;

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.