package ocamlregextkit

  1. Overview
  2. Docs

Module Regextkit.NfaSource

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

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