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_graph_attribute($_[0], 'label')
    },
    successors   => sub { $g->successors($_[0]) },
    get_label    => sub {
      $g->get_graph_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

A start state for the initial configuration of the automaton.

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.

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 function construct_dfa by default.

AUTHOR / COPYRIGHT / LICENSE

  Copyright (c) 2014 Bjoern Hoehrmann <bjoern@hoehrmann.de>.
  This module is licensed under the same terms as Perl itself.