Forlan Manual


The DFA Module


Synopsis

signature DFA
structure DFA :> DFA

This module defines the abstract type of deterministic finite automata (DFAs).


Interface

type dfa
val injToFA : dfa -> FA.fa
val injToEFA : dfa -> EFA.efa
val injToNFA : dfa -> NFA.nfa
val valid : FA.fa -> bool
val projFromFA : FA.fa -> dfa
val projFromEFA : EFA.efa -> dfa
val projFromNFA : NFA.nfa -> dfa
val fromString : string -> dfa
val input : string -> dfa
val toPP : dfa -> PP.pp
val toString : dfa -> string
val output : string * dfa -> unit
val states : dfa -> Sym.sym Set.set
val startState : dfa -> Sym.sym
val acceptingStates : dfa -> Sym.sym Set.set
val transitions : dfa -> Tran.tran Set.set
val compare : dfa Sort.total_ordering
val equal : dfa * dfa -> bool
val numStates : dfa -> int
val numTransitions : dfa -> int
val alphabet : dfa -> Sym.sym Set.set
val sub : dfa * dfa -> bool
val transitionFun : dfa -> Sym.sym * Str.str -> Sym.sym Set.set
val transitionFunBackwards : dfa -> Sym.sym * Str.str -> Sym.sym Set.set
val processStr : dfa -> Sym.sym Set.set * Str.str -> Sym.sym Set.set
val accepted : dfa -> Str.str -> bool
val reachify : dfa -> dfa
val reachified : dfa -> bool
val renameStates : dfa * SymRel.sym_rel -> dfa
val renameStatesCanonically : dfa -> dfa
val isomorphism : dfa * dfa * SymRel.sym_rel -> bool
val findIsomorphismOpt : dfa * dfa -> SymRel.sym_rel option
val findIsomorphism : dfa * dfa -> SymRel.sym_rel
val isomorphic : dfa * dfa -> bool
val renameAlphabet : dfa * SymRel.sym_rel -> dfa
val checkLP : dfa -> LP.lp -> unit
val validLP : dfa -> LP.lp -> bool
val findLPOpt : dfa -> Sym.sym Set.set * Str.str * Sym.sym Set.set -> LP.lp option
val findLP : dfa -> Sym.sym Set.set * Str.str * Sym.sym Set.set -> LP.lp
val findAcceptingLPOpt : dfa -> Str.str -> LP.lp option
val findAcceptingLP : dfa -> Str.str -> LP.lp
val emptyStr : dfa
val emptySet : dfa
val inter : dfa * dfa -> dfa
val genInter : dfa list -> dfa
val determTransitionFun : dfa -> Sym.sym * Sym.sym -> Sym.sym
val determProcessStr : dfa -> Sym.sym * Str.str -> Sym.sym
val determAccepted : dfa -> Str.str -> bool
val fromNFA : NFA.nfa -> dfa
val determSimplified : dfa -> bool
val determSimplify : dfa * Sym.sym Set.set -> dfa
val minimize : dfa -> dfa
val complement : dfa * Sym.sym Set.set -> dfa
val minus : dfa * dfa -> dfa
datatype relationship
  = Equal
  | ProperSub of Str.str
  | ProperSup of Str.str
  | Incomp of Str.str * Str.str
val relation : dfa * dfa -> relationship
val relationship : dfa * dfa -> unit
val subset : dfa * dfa -> bool
val equivalent : dfa * dfa -> bool

Description

type dfa
The abstract type of DFAs, which is a proper subset of the set of FAs.

injToFA dfa
inject dfa to have type FA.fa.

injToEFA df
inject dfa to have type EFA.efa.

injToNFA dfa
inject dfa to have type NFA.nfa.

valid fa
tests whether fa is a DFA.

projFromFA fa
projects fa to have type dfa. Issues an error message if fa is not a DFA.

projFromEFA efa
projects efa to have type dfa. Issues an error message if efa is not a DFA.

projFromNFA nfa
projects nfa to have type nfa. Issues an error message if nfa is not a DFA.

fromString s
inputs a DFA from s.

input fil
inputs a DFA from the file named fil.

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

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

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

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

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

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

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

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

equal(dfa1, dfa2)
tests whether dfa1 and dfa2 are equal. (Inherited from FA.)

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

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

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

sub(dfa1, dfa2)
tests whether dfa1 is a sub-DFA of dfa2. (Inherited from FA.)

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

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

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

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

reachify dfa
reachifies dfa. (Inherited from FA.)

reachified dfa
tests whether dfa is reachified. (Inherited from FA.)

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

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

isomorphism(dfa1, dfa2, rel)
tests whether rel is an isomorphism from dfa1 to dfa2. (Inherited from FA.)

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

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

isomorphic(dfa1, dfa2)
tests whether dfa1 and dfa2 are isomorphic. (Inherited from FA.)

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

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

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

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

findLP dfa (qs, x, rs)
tries to find a minimal labeled path for dfa, 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 dfa, or such a labeled path doesn't exist. (Inherited from FA.)

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

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

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

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

inter(dfa1, dfa2)
returns the intersection of dfa1 and dfa2. (Inherited from EFA.)

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


determTransitionFun dfa (q, a)
returns the unique state r such that (q, [a], r) is a transition of dfa. Issues an error message if q is not a state of dfa, or a is not a member of the alphabet of dfa.

determProcessStr dfa (q, x)
uses determTransitionFun to deterministically process x from q in dfa, returning the resulting state. Issues an error message if q is not a state of dfa, or there is a symbol of x that is not in the alphabet of dfa.

determAccepted dfa x
uses determProcessStr to test whether x is accepted by dfa.

fromNFA nfa
converts nfa to a DFA.

determSimplified dfa
tests whether dfa is deterministically simplified.

determSimplify(dfa, bs)
deterministically simplifies dfa, with reference to bs.

minimize dfa
minimizes dfa.

complement(dfa, bs)
returns the complement of dfa, with reference to bs.

minus(dfa1, dfa2)
returns the difference of dfa1 and dfa2.

datatype relationship
  = Equal
  | ProperSub of Str.str
  | ProperSup of Str.str
  | Incomp of Str.str * Str.str
Datatype used by relation function.

relation(dfa1, dfa2)
determines the relationship between the language accepted by dfa1 and the language accepted by dfa2:

relationship(dfa1, dfa2)
explains the significance of the result of evaluating relation(dfa1, dfa2).

subset(dfa1, dfa2)
uses relation to test whether the language accepted by dfa1 is a subset of the language accepted by dfa2.

equivalent(dfa1, dfa2)
uses relation to test whether dfa1 and dfa2 are equivalent.


[ Top | Parent | Root | Contents | Index ]

Forlan Version 4.12
Copyright © 2019 Alley Stoughton