The ppRegExpFm functor

Synopsis

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 E.re
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


Description

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 E.re


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 s.dot and s.ps 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

LABEL, PPREGEXP, PPFM

Discussion

Example:

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";