The ppRegEqnsFm functor

Synopsis

signature PPREGEQNSFM
functor ppRegEqnsFm (NAMES) : PPREGEQNSFM


This functor generates funtions that translate between regular recursion equations 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
type 'a eqns = 'a re E.eqns
val printExp : label re -> unit
val printEqns : label eqns -> 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 recursion equations, 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


type 'a eqns = 'a re E.eqns


the type of regular recursion equations over alphabets of type 'a.

printExp r

prints the expression r.

printEqns eqs

prints the system eqs of regular recursion equations, using the printnames provided by the input structure.

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

NAMES, PPREGEXP, PPFM

Discussion

Example:

A finite machine is translated to a (right-linear) system of recursion equations and then printed:

structure StringNames = Names(StringLabels);
structure ppEM = ppRegEqnsFm(StringNames)

open ppEM;

val ndM = M.make{trans = [(0,"a",1),(0,"a",2),
                          (1,"a",0),(1,"b",2),
                          (2,"b",0),(2,"b",1)], 
                 start=[0,2],
                 final=[1,2]};

printEqns(fmToEqns ndM);

The equation system is printed as follows:

 Equation system: 
   x_0 = (a;x_1 + a;x_2)
   x_1 = (1 + a;x_0 + b;x_2)
   x_2 = (1 + b;x_0 + b;x_1)
   x_3 = (x_0 + x_2)

The first variables correspond to the states of the machine; the last variable defines the sum of the components corresponding to the initial states.