package ocamlregextkit

  1. Overview
  2. Docs

Module Regextkit.DfaSource

Representation of DFAs and implementation of standard operations

Sourcetype state =
  1. | State of int list
  2. | 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

Sourceval 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 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

Sourceval product_difference : dfa -> dfa -> dfa

product_difference m1 m2

  • returns

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

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

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