NAME
Algorithm::ConstructDFA  Deterministic finite automaton construction
SYNOPSIS
use Algorithm::ConstructDFA;
my $dfa = construct_dfa(
start => [ $start_vertex ],
is_accepting => sub { grep { $_ eq $final_vertex } @_ },
is_nullable => sub {
$g>has_vertex_attribute($_[0], 'label')
},
successors => sub { $g>successors($_[0]) },
get_label => sub {
$g>get_vertex_attribute($_[0], 'label')
},
);
DESCRIPTION
This module provides a generic deterministic finite automaton construction function. The input model is a graph with possibly labeled (usually with "nonterminals") vertices. Edges in the graph are always unlabeled.
FUNCTIONS
 construct_dfa(%options)

Construct a DFA using the given options.
 start

An array of start states for the initial configuration of the automaton.
 final

An array of final accepting states. This can be used instead of specifying a subroutine in
is_accepting
.  is_accepting

A subroutine returning a boolean indicating whether this is an accepting final state of the automaton. It is passed all the vertices the states combines. For singlevertex acceptance, it would usually
grep
over the arguments. Having access to all the states of the input automaton allows more complex acceptance conditions (e.g. to compute the intersection of two graphs).  is_nullable

A subroutine returning a boolean indicating whether the automaton can move past the supplied state without consuming any input.
 successors

A subroutine that returns a list of all immediate successors of the given vertex.
 get_label

A subroutine that returns a callerdefined string representing what kind of input is expected to move past the supplied vertex. Can also be
undef
for vertices without label.
The function returns the DFA as hash reference with integer keys. The key
0
is a nonaccepting state with no transitions to other states (the automaton would go into this state if the match has failed). The key1
is the start state. The value of each entry is another hash reference. As an example:'1': Accepts: 1 Combines:  0  1  2 NextOver: a: 0 b: 1
The
Accepts
key indicates whether this is an accepting state. TheCombines
key provides access to the list of states in the input automaton this DFA state corresponds to. TheNextOver
field is the transition table out of this state. This automaton matches any sequence of zero or moreb
s. The alphabet also includes the labela
but the automaton moves from the start state over the labela
to the nonaccepting sink state0
and would never enter an accepting state after that.An exception to the rule above is when
is_accepting
returns a true value when passed no arguments (i.e., the automaton accepts when it is in none of the states in the input automaton). Then state0
is made an accepting state (and combines states from which the final vertex is unreachable as before). This can be useful to compute complement graphs.
EXPORTS
The functions construct_dfa
and construct_dfa_as_graph
by default.
AUTHOR / COPYRIGHT / LICENSE
Copyright (c) 2014 Bjoern Hoehrmann <bjoern@hoehrmann.de>.
This module is licensed under the same terms as Perl itself.