NAME

FLAT::NFA - Nondeterministic finite automata

SYNOPSIS

A FLAT::NFA object is a finite automata whose transitions are labeled either with characters or the empty string (epsilon).

USAGE

In addition to implementing the interface specified in FLAT, FLAT::NFA objects provide the following NFA-specific methods:

$nfa->epsilon_closure(@states)

Returns the set of states (without duplicates) which are reachable from @states via zero or more epsilon-labeled transitions.

$nfa->trace($string)

Returns a list of N+1 arrayrefs, where N is the length of $string. The I-th arrayref contains the states which are reachable from the starting state(s) of $nfa after reading I characters of $string. Correctly accounts for epsilon transitions.

$nfa->as_undirected

Outputs FA in a format that may be easily read into an external program as a description of an undirected graph.

$nfa->as_digraph

Outputs FA in a format that may be easily read into an external program as a description of an directed graph.

$nfa->as_gdl

Outputs FA in Graph Description Language (GDL), including directed transitions with symbols and state names labeled.

$nfa->as_graphviz

Outputs FA in Graphviz format, including directed transitions with symbols and and state names labeled. This output may be directly piped into any of the Graphviz layout programs, and in turn one may output an image using a single commandline instruction. fash uses this function to implement its "nfa2gv" command:

fash nfa2gv "a*b" | dot -Tpng > nfa.png

$nfa->as_undirected_graphviz

Outputs FA in Graphviz format, with out the directed transitions or labels. The output is suitable for any of the Graphvize layout programs, as discussed above.

$nfa->as_summary

Outputs a summary of the FA, including its states, symbols, and transition matrix. It is useful for manually validating what the FA looks like.

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.