package ocamlregextkit

  1. Overview
  2. Docs
Legend:
Library
Module
Module type
Parameter
Class
Class type

Representation of DFAs and implementation of standard operations

type state =
  1. | State of int list
  2. | ProductState of state * state
type dfa
val get_states : dfa -> state list

get_states m

  • returns

    a list of all states in DFA m

val get_alphabet : dfa -> string list

get_alphabet m

  • returns

    the alphabet of DFA m as a list

val 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)

val get_start : dfa -> state

get_start m

  • returns

    the initial state of DFA m

val get_accepting : dfa -> state list

get_accepting m

  • returns

    a list of all accepting states in DFA m

val is_accepting : dfa -> state -> bool

is_accepting m s

  • returns

    true iff state s is an accepting state of DFA m

val succ : dfa -> state -> string -> state

succ m s w

  • returns

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

val 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

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

val copy : dfa -> dfa

copy m

  • returns

    a deep copy of DFA m

val complement : dfa -> dfa

complement m

  • returns

    the complement of DFA m

val reachable_states : dfa -> state list

reachable_states m

  • returns

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

val prune : dfa -> unit

prune m mutates DFA inplace m by removing unreachable states

val is_empty : dfa -> bool

is_empty m

  • returns

    true iff DFA m is empty

val is_accepted : dfa -> string -> bool

is_accepted m s

  • returns

    true iff DFA m accepts string s

val get_accepted : dfa -> string option

get_accepted m

  • returns

    the shortest string accepted by DFA m

val 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

val 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

val product_union : dfa -> dfa -> dfa

product_union m1 m2

  • returns

    the union of DFAs m1 m2, by the product construction

val 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

val symmetric_equiv : dfa -> dfa -> bool

symmetric_equiv m1 m2

  • returns

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

val 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

val myhill_min : dfa -> unit

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

val hopcroft_min : dfa -> unit

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

val brzozowski_min : dfa -> dfa

brzozowski_min m

  • returns

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

val minimise : dfa -> unit

minimise m synonym for hopcroft_min m

  • returns

    minimisation of DFA m

val nfa_to_dfa : Nfa.nfa -> dfa

nfa_to_dfa m

  • returns

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

val re_to_dfa : Tree.re -> dfa

re_to_dfa re

  • returns

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

val print : dfa -> unit

print m prints a string representation of the DFA m

val export_graphviz : dfa -> string

export_graphviz m

  • returns

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

OCaml

Innovation. Community. Security.