Forlan Manual

The NFA Module

Synopsis

signature NFA
structure NFA :> NFA

This module defines the abstract type of nondeterministic finite automata (NFAs).

Interface

type nfa
val injToFA : nfa -> FA.fa
val injToEFA : nfa -> EFA.efa
val valid : FA.fa -> bool
val projFromFA : FA.fa -> nfa
val projFromEFA : EFA.efa -> nfa
val fromString : string -> nfa
val input : string -> nfa
val toPP : nfa -> PP.pp
val toString : nfa -> string
val output : string * nfa -> unit
val states : nfa -> Sym.sym Set.set
val startState : nfa -> Sym.sym
val acceptingStates : nfa -> Sym.sym Set.set
val transitions : nfa -> Tran.tran Set.set
val compare : nfa Sort.total_ordering
val equal : nfa * nfa -> bool
val numStates : nfa -> int
val numTransitions : nfa -> int
val alphabet : nfa -> Sym.sym Set.set
val sub : nfa * nfa -> bool
val transitionFun : nfa -> Sym.sym * Str.str -> Sym.sym Set.set
val transitionFunBackwards : nfa -> Sym.sym * Str.str -> Sym.sym Set.set
val processStr : nfa -> Sym.sym Set.set * Str.str -> Sym.sym Set.set
val accepted : nfa -> Str.str -> bool
val reachableStates : nfa -> Sym.sym Set.set
val liveStates : nfa -> Sym.sym Set.set
val deadStates : nfa -> Sym.sym Set.set
val renameStates : nfa * SymRel.sym_rel -> nfa
val renameStatesCanonically : nfa -> nfa
val isomorphism : nfa * nfa * SymRel.sym_rel -> bool
val findIsomorphismOpt : nfa * nfa -> SymRel.sym_rel option
val findIsomorphism : nfa * nfa -> SymRel.sym_rel
val isomorphic : nfa * nfa -> bool
val renameAlphabet : nfa * SymRel.sym_rel -> nfa
val checkLP : nfa -> LP.lp -> unit
val validLP : nfa -> LP.lp -> bool
val findLPOpt : nfa -> Sym.sym Set.set * Str.str * Sym.sym Set.set -> LP.lp option
val findLP : nfa -> Sym.sym Set.set * Str.str * Sym.sym Set.set -> LP.lp
val findAcceptingLPOpt : nfa -> Str.str -> LP.lp option
val findAcceptingLP : nfa -> Str.str -> LP.lp
val emptyStr : nfa
val emptySet : nfa
val fromSym : Sym.sym -> nfa
val simplify : nfa -> nfa
val simplified : nfa -> bool
val inter : nfa * nfa -> nfa
val genInter : nfa list -> nfa
val prefix : nfa -> nfa
val fromEFA : EFA.efa -> nfa

Description

type nfa
The abstract type of NFAs, which is a proper subset of the set of EFAs (and thus FAs).

injToFA nfa
inject nfa to have type FA.fa.

injToEFA nfa
inject nfa to have type EFA.efa.

valid fa
tests whether fa is an NFA.

projFromFA fa
projects fa to have type nfa. Issues an error message if fa is not an NFA.

projFromEFA efa
projects efa to have type nfa. Issues an error message if efa is not an NFA.

fromString s
inputs an NFA from a string.

input fil
inputs an NFA from the file named fil.

toPP fa
returns a pretty-printing expression for nfa. (Inherited from FA.)

toString nfa
pretty-prints nfa to a string. (Inherited from FA.)

output(fil, nfa)
pretty-prints nfa to the file fil. (Inherited from FA.)

states nfa
returns the states of nfa. (Inherited from FA.)

startState nfa
returns the start state of nfa. (Inherited from FA.)

acceptingStates nfa
returns the accepting states of nfa. (Inherited from FA.)

transitions nfa
returns the transitions of nfa. (Inherited from FA.)

compare(nfa1, nfa2)
compares nfa1 and nfa2 in the total ordering on FAs. (Inherited from FA.)

equal(nfa1, nfa2)
tests whether nfa1 and nfa2 are equal. (Inherited from FA.)

numStates nfa
returns the number of states of nfa. (Inherited from FA.)

numTransitions nfa
returns the number of transitions of nfa. (Inherited from FA.)

alphabet nfa
returns the alphabet of nfa. (Inherited from FA.)

sub(nfa1, nfa2)
tests whether nfa1 is a sub-NFA of nfa2. (Inherited from FA.)

transitionFun nfa (q, x)
returns the set of all states r such that (q, x, r) is a transition of nfa. Issues an error message if q is not a state of nfa. (Inherited from FA.)

transitionFunBackwards nfa (r, x)
returns the set of all states q such that (q, x, r) is a transition of nfa. Issues an error message if r is not a state of nfa. (Inherited from FA.)

processStr nfa (qs, x)
processes x from qs in nfa. Issues an error message if qs has an element that's not a state of nfa. (Inherited from FA.)

accepted nfa x
tests whether x is accepted by nfa. (Inherited from FA.)

reachableStates nfa
returns the set of all reachable states of nfa.

liveStates nfa
returns the set of all live states of nfa.

deadStates nfa
returns the set of all dead states of nfa.

renameStates(nfa, rel)
renames the states of nfa using the bijection rel. Issues an error message if rel is not a bijection from the states of nfa to some set. (Inherited from FA.)

renameStatesCanonically nfa
canonically renames the states of nfa. (Inherited from FA.)

isomorphism(nfa1, nfa2, rel)
tests whether rel is an isomorphism from nfa1 to nfa2. (Inherited from FA.)

findIsomorphismOpt(nfa1, nfa2)
returns SOME of an isomorphism from nfa1 to nfa2, if nfa1 and nfa2 are isomorphic, and NONE, if nfa1 and nfa2 are not isomorphic.

findIsomorphism(nfa1, nfa2)
tries to find an isomorphism from nfa1 to nfa2. Issues an error message if such an isomorphism doesn't exist. (Inherited from FA.)

isomorphic(nfa1, nfa2)
tests whether nfa1 and nfa2 are isomorphic. (Inherited from FA.)

renameAlphabet(nfa, rel)
renames the alphabet of nfa using the bijection rel. Issues an error message if rel is not a bijection from a superset of the alphabet of nfa to some set. (Inherited from FA.)

checkLP nfa lp
checks whether lp is valid for nfa, silently returning (), if it is, and explaining why it isn't, if it's not. (Inherited from FA.)

validLP nfa lp
tests whether lp is valid for nfa. (Inherited from FA.)

findLPOpt nfa (qs, x, rs)
returns SOME of a minimal labeled path for nfa, taking qs to rs with label x, if such a labeled path exists, and NONE, if such a labeled path does not exist.

findLP nfa (qs, x, rs)
tries to find a minimal labeled path for nfa, taking qs to rs with label x. Issues an error message if there is an element of qs or rs that isn't a state of nfa, or such a labeled path doesn't exist. (Inherited from FA.)

findAcceptingLPOpt nfa x
returns SOME of a minimal, accepting labeled path for nfa and x, if such a labeled path exists, and NONE, if such a labeled path doesn't exist.

findAcceptingLP nfa x
tries to find a minimal, accepting labeled path for nfa and x. Issues an error message if such a labeled path doesn't exist. (Inherited from FA.)

emptyStr
is the canonical NFA for the empty string. (Inherited from FA.)

emptySet
is the canonical NFA for the empty set. (Inherited from FA.)

fromSym a
returns the canonical NFA for a. (Inherited from FA.)

simplify nfa
simplifies nfa. (Inherited from FA.)

simplified nfa
tests whether nfa is simplified. (Inherited from FA.)

inter(nfa1, nfa2)
returns the intersection of nfa1 and nfa2. (Inherited from EFA.)

genInter
is defined by: 
  fun genInter nil           = (* issues an error message *)
    | genInter [nfa]         = nfa
    | genInter (nfa :: nfas) = inter(inter, genInter nfas)


prefix nfa
returns the prefix-closure of nfa. (Inherited from EFA.)

fromEFA efa
converts efa to an NFA.

[ Top | Parent | Root | Contents | Index ]

Forlan Version 4.15
Copyright © 2022 Alley Stoughton