Functional composition of lazy deterministic finite automata.
This module implements operators for functional composition of lazy deterministic finite automata (DFA). A DFA is computationally more efficient at recognizing regular grammars than a non-deterministic finite automaton, at the cost of requiring exponentially more space for states. Lazy computation and memorization of DFA states usually requires space comparable with direct NFA elaboration, at the cost of some additional computation required when new DFA states are encountered.
module type Dispatch = sig ... endThis signature provides the abstraction necessary to represent an event dispatch, which is part of the DFA state record. It creates a dispatch for each new DFA state computed. It conceptually represents a lazily-evaluated map of events to state transitions.
module type Basis = sig ... endThis signature is a the basis for creating a DFA module.
module Aux : sig ... endThis module contains some pre-defined dispatch modules.
module type Regular = sig ... endThe signature of the core functions of the DFA engine.
module type Machine = sig ... endmodule type Affix = sig ... endThe signature of additional affix operators for composing terms.
module Mk_affix
(R : Regular) :
Affix
with type event := R.event
and type term := R.term
and type 'r fin := 'r R.finUse Mk_affix(R) to make the optional affix operators for R.
module type Profile = sig ... endThe DFA signature including the affix operators.