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 "non-terminals") 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 single-vertex 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 caller-defined 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 non-accepting state with no transitions to other states (the automaton would go into this state if the match has failed). The key 1 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. The Combines key provides access to the list of states in the input automaton this DFA state corresponds to. The NextOver field is the transition table out of this state. This automaton matches any sequence of zero or more bs. The alphabet also includes the label a but the automaton moves from the start state over the label a to the non-accepting sink state 0 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 state 0 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.