ocamlregextkit 0.1.1 · OCaml Package

Representation of NFAs and implementation of standard operations

type state = int

type nfa

val get_states : nfa -> state list

get_states n

returns
a list of all states in NFA n

val get_alphabet : nfa -> string list

get_alphabet n

returns
the alphabet of NFA n as a list

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

val get_start : nfa -> state

get_start n

returns
the initial state of NFA n

val get_accepting : nfa -> state list

get_accepting n

returns
a list of all accepting states in NFA n

val is_accepting : nfa -> state -> bool

is_accepting n s

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

val 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

val pred : nfa -> state -> state list

pred n s

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

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

val re_to_nfa : Tree.re -> nfa

re_to_nfa r

returns
an NFA constructed from the RE r

val 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

val reachable_states : nfa -> state list

reachable_states n

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

val prune : nfa -> nfa

prune n

returns
a reduction of NFA n by removing unreachable states

val is_empty : nfa -> bool

is_empty n

returns
true iff NFA n is empty

val is_accepted : nfa -> string -> bool

is_accepted n s

returns
true iff NFA n accepts string s

val get_accepted : nfa -> string option

get_accepted n

returns
the shortest string accepted by NFA n

val merge_alphabets : nfa -> nfa -> nfa * nfa

merge_alphabets n1 n2

returns
a tuple of NFAs (n1', n2') such that n1' and n2' both share a common alphabet

val print : nfa -> unit

print n prints a string representation of the NFA n

val export_graphviz : nfa -> string

export_graphviz n

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

package ocamlregextkit