NAME

FLAT::FA - Base class for regular finite automata

SYNOPSIS

A FLAT::FA object is a collection of states and transitions. Each state may be labeled as starting or accepting. Each transition between states is labeled with a transition object.

USAGE

FLAT::FA is a superclass that is not intended to be used directly. However, it does provide the following methods:

Manipulation & Inspection Of States

$fa->get_states

Returns a list of all the state "names" in $fa.

$fa->num_states

Returns the number of states in $fa.

$fa->is_state($state_id)

Returns a boolean indicating whether $state_id is a recognized state "name."

$fa->delete_states(@states)

Deletes the states given in @states and their corresponding transitions. The remaining states in the FA may be "renamed" (renumbered)! Return value not used.

$fa->add_states($num)

Adds $num states to $fa, and returns a list of the new state "names."

$fa->get_starting

$fa->get_accepting

Returns a list of all the states which are labeled as starting/accepting, respectively.

$fa->set_accepting(@states)

$fa->unset_accepting(@states)

$fa->set_starting(@states)

$fa->unset_starting(@states)

Sets/unsets a list of states as being labeled starting/accepting, respectively.

$fa->is_starting($state)

$fa->is_accepting($state)

Returns a boolean indicating whether $state is labeled as starting/accepting, respectively.

$fa->prune

Deletes the states which are not reachable (via zero or more transitions) from starting states. Returns a list of the "names" of states that were deleted.

Manipulation & Inspection Of Transitions

Each transition between states is a transition object, which knows how to organize several "labels." Think of this as the mechanism by which multiple arrows in the state diagram between the same states are collapsed to a single arrow. This interface is abstracted away into the following public methods:

$fa->set_transition($state1, $state2, @labels)

Resets the transition between $state1 and $state2 to a transition initialized using data @labels. If @labels is omitted or contains only undefined elements, then the call is equivalent to remove_transition.

$fa->add_transition($state1, $state2, @labels)

Adds @labels to the transition between $state1 and $state2.

$fa->get_transition($state1, $state2)

Returns the transition object stored between $state1 and $state2, or undef if there is no transition.

$fa->remove_transition($state1, $state2)

Removes the transition object between $state1 and $state2.

$fa->successors(\@states)

$fa->successors($state)

$fa->successors(\@states, $label)

$fa->successors($state, $label)

$fa->successors(\@states, \@labels)

$fa->successors($state, \@labels)

Given a state/set of states, and one or more labels, returns a list of the states (without duplicates) reachable from the states via a single transition having any of the given labels. If no labels are given, returns the states reachable by any (single) transition.

Note that this method makes no distinction for epsilon transitions, these are only special in FLAT::NFA objects.

$fa->alphabet

Returns the list of characters (without duplicates) used among all transition labels in the automaton.

Conversions To External Formats

$fa->as_graphviz

Returns a string containing a GraphViz (dot) description of the automaton, suitable for rendering with your favorite GraphViz layout engine.

$fa->as_summary

Returns a string containing a plaintext description of the automaton, suitable for debugging purposes.

Miscellaneous

$fa->clone

Returns an identical copy of $fa.

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.