Module `Regextkit.Nfa`Source

Representation of NFAs and implementation of standard operations

Sourcetype state = int

Sourcetype nfa

Sourceval get_states : nfa -> state list

get_states n

returns
a list of all states in NFA n

Sourceval get_alphabet : nfa -> string list

get_alphabet n

returns
the alphabet of NFA n as a list

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

get_transitions n

returns
the transition function of NFA n as a list of tuples (s,a,t)

Sourceval get_start : nfa -> state

get_start n

returns
the initial state of NFA n

Sourceval get_accepting : nfa -> state list

get_accepting n

returns
a list of all accepting states in NFA n

Sourceval is_accepting : nfa -> state -> bool

is_accepting n s

returns
true iff state s is an accepting state of NFA n

Sourceval succ : nfa -> state -> string -> state list

succ n s w

returns
a list of successor states of NFA n after reading word w from state s

Sourceval pred : nfa -> state -> state list

pred n s

returns
a list of states that preceed the state s in NFA n

Source

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

create q al t s f

returns
the NFA of States q, alphabet al, transition function t, initial state s, and accepting states f. Note that states will be renamed to integers.

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 is not a valid tranition function for states qs and alphabet al

Sourceval copy : nfa -> nfa

copy n

returns
a deep copy of NFA n

Sourceval re_to_nfa : Tree.re -> nfa

re_to_nfa r

returns
an NFA constructed from the RE r

Sourceval eps_reachable_set : nfa -> state list -> state list

eps_reachable_set n ss

returns
the set of all epsilon reachable states in the NFA n from the set of states ss

Sourceval reachable_states : nfa -> state list

reachable_states n

returns
the set of reachable (connected) states in the NFA n

Sourceval prune : nfa -> unit

prune n mutates DFA n by removing unreachable states

Sourceval is_empty : nfa -> bool

is_empty n

returns
true iff NFA n is empty

Sourceval is_accepted : nfa -> string -> bool

is_accepted n s

returns
true iff NFA n accepts string s

Sourceval get_accepted : nfa -> string option

get_accepted n

returns
the shortest string accepted by NFA n

Sourceval merge_alphabets : nfa -> nfa -> unit

merge_alphabets n1 n2 mutates NFAs n1 and n2 such that they share a common alphabet

Sourceval print : nfa -> unit

print n prints a string representation of the NFA n

Sourceval export_graphviz : nfa -> string

export_graphviz n

returns
a representation of the NFA n in the DOT language for Graphviz

package ocamlregextkit

Module Regextkit.NfaSource

Module `Regextkit.Nfa`Source