Module `Regextkit.Dfa`Source

Representation of DFAs and implementation of standard operations

Sourcetype state =

| State of int list
| ProductState of state * state

Sourcetype dfa

Sourceval get_states : dfa -> state list

get_states m

returns
a list of all states in DFA m

Sourceval get_alphabet : dfa -> string list

get_alphabet m

returns
the alphabet of DFA m as a list

Sourceval get_transitions : dfa -> (state * string * state) list

get_transitions m

returns
the transition function of DFA m as a list of tuples (s,a,t)

Sourceval get_start : dfa -> state

get_start m

returns
the initial state of DFA m

Sourceval get_accepting : dfa -> state list

get_accepting m

returns
a list of all accepting states in DFA m

Sourceval is_accepting : dfa -> state -> bool

is_accepting m s

returns
true iff state s is an accepting state of DFA m

Sourceval succ : dfa -> state -> string -> state

succ m s w

returns
the successor state of DFA m after reading word w from state s

Sourceval pred : dfa -> state -> string -> state list

pred m s w

returns
the set of predecessor states of DFA m before reading word w from state s

Source

val create : 
  'a list ->
  string list ->
  ('a * string * 'a) list ->
  'a ->
  'a list ->
  dfa

create q al t s f

returns
the DFA of States q, alphabet al, transition function t, initial state s, and accepting states f. Note that states will be renamed to integer list. Sink state will be added to make transition function t total.

raises Invalid_argument
if s is not a valid state in q

raises Invalid_argument
if f is not a valid subset of q

raises Invalid_argument
if t contains epsilon-transitions.

raises Invalid_argument
if t is not a valid tranition function for states qs and alphabet al

Sourceval copy : dfa -> dfa

copy m

returns
a deep copy of DFA m

Sourceval complement : dfa -> dfa

complement m

returns
the complement of DFA m

Sourceval reachable_states : dfa -> state list

reachable_states m

returns
the set of reachable (connected) states in the DFA m

Sourceval prune : dfa -> unit

prune m mutates DFA inplace m by removing unreachable states

Sourceval is_empty : dfa -> bool

is_empty m

returns
true iff DFA m is empty

Sourceval is_accepted : dfa -> string -> bool

is_accepted m s

returns
true iff DFA m accepts string s

Sourceval get_accepted : dfa -> string option

get_accepted m

returns
the shortest string accepted by DFA m

Sourceval product_intersection : dfa -> dfa -> dfa

product_insterection m1 m2

returns
the intersection of DFAs m1 m2, by the product construction

raises Invalid_argument
if m1 and m2 have different alphabets

Sourceval product_difference : dfa -> dfa -> dfa

product_difference m1 m2

returns
the symmetric difference of DFAs m1 m2, by the product construction

raises Invalid_argument
if m1 and m2 have different alphabets

Sourceval product_union : dfa -> dfa -> dfa

product_union m1 m2

returns
the union of DFAs m1 m2, by the product construction

Sourceval hopcroft_equiv : dfa -> dfa -> bool

hopcroft_equiv m1 m2

returns
true iff the two DFAs m1 and m2 are equivalent, by Hopcroft's algorithm

raises Invalid_argument
if m1 and m2 have different alphabets

Sourceval symmetric_equiv : dfa -> dfa -> bool

symmetric_equiv m1 m2

returns
true iff the two DFAs m1 and m2 are equivalent, by symmetric difference

Sourceval is_equiv : dfa -> dfa -> bool

is_equiv m1 m2 synonym for hopcroft_equiv m1 m2

returns
true iff the two DFAs m1 and m2 are equivalent

Sourceval myhill_min : dfa -> unit

myhill_min m minimises DFA m inplace, by Myhill-Nerode theorem

Sourceval hopcroft_min : dfa -> unit

hopcroft_min m minimises DFA m inplace, by Hopcroft's algorithm

Sourceval brzozowski_min : dfa -> dfa

brzozowski_min m

returns
minimisation of DFA m, by Brzozowski's algorithm. Note that states will be renamed.

Sourceval minimise : dfa -> unit

minimise m synonym for hopcroft_min m

returns
minimisation of DFA m

Sourceval nfa_to_dfa : Nfa.nfa -> dfa

nfa_to_dfa m

returns
the NFA equivalent to DFA m, by an optimised subset construction

Sourceval re_to_dfa : Tree.re -> dfa

re_to_dfa re

returns
a DFA recognising the language of re, by Brzozowski's construction

Sourceval print : dfa -> unit

print m prints a string representation of the DFA m

Sourceval export_graphviz : dfa -> string

export_graphviz m

returns
a representation of the DFA m in the DOT language for Graphviz

package ocamlregextkit

Module Regextkit.DfaSource

Module `Regextkit.Dfa`Source