The ppRegExpFm functor


signature PPREGEXPFM
functor ppRegExpFm (LABEL) : PPREGEXPFM

This functor generates funtions that translate between regular expressions (without variables) and finite automata (without epsilon-transitions). Moreover, printing functions for regular expressions and displaying of finite automata are generated, using printnames as provided by the argument structure.

More detailed printing functions showing equivalence classes of states are contained in the substructure M.

Functor result interface

structure E : PPREGEQNS
structure M : PPFM
sharing type M.label = E.alph
type ''a machine = ''a M.machine
type label = M.label
datatype re = datatype
val printExp : label re -> unit
val accept : ''a machine -> ''a list -> bool
val display : label machine -> string -> OS.Process.status
val retofm : ''a re -> ''a machine
val retominfm : ''a re -> ''a machine
val fmtore : ''a machine -> ''a re


structure E : PPREGEQNS
a structure of regular expression and equation systems, using printnames provided by the input structure.

structure M : PPFM
a structure for finite automata, using printnames provided by the input structure.

sharing type M.label = E.alph

type ''a machine = ''a M.machine

type label = M.label

datatype re = datatype

printExp r
prints the expression r.

accept m l
returns true if m reaches an accepting state after executing instructions l.

display m s
displays machine m using ATT's graph drawing program dot. Writes files and that can be manipulated further, or included in documents.

retofm r
returns a finite automaton m accepting the language defined by expression r. The expression r must not have free variables. (no error message yet)

retominfm r
returns a state-minimal (total) deterministic finite automation m accepting the language defined by r. (Expression r must not have free variables.)

fmtore m
returns a regular expression r definining the language accepted by machine m.

See Also




Translation from regular expressions (a+b)^*a(a+b)^n to finite machines; minimal deterministic version is exponential in n:

structure Tr = ppRegExpFm(StringLabels);

val a = Tr.E.Atom "a" and b = Tr.E.Atom "b";

fun expr n = Tr.E.Times[Tr.E.Star(Tr.E.Plus[a,b]),a,Tr.E.Power (Tr.E.Plus[a,b]) n]
and mach n = Tr.retominfm (expr n);

Tr.display (mach 2) "testfile";