The RegEqnsFm structure


Synopsis

signature REGEQNSFM
structure RegEqnsFm : REGEQNSFM

This structure combines the structure RegEqns for regular recursion equations with the structure Fm for finite machines.


Interface

structure E : REGEQNS
structure M : FM
type ''a machine = ''a M.machine
datatype re = datatype E.re
val accept : ''a machine -> ''a list -> bool
val retofm : ''a re -> ''a machine
val retominfm : ''a re -> ''a machine
val fmtore : ''a machine -> ''a re
val fmToEqns : ''a machine -> ''a re E.eqns

Description

structure E : REGEQNS
the structure RegEqns dealing with regular equation systems.

structure M : FM
the structure Fm dealing with finite machines.

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

datatype re = datatype E.re

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

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 the state-minimal deterministic finite automaton m accepting the language defined by expression r. The expression r must not have free variables. (no error message yet)

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

fmToEqns m
returns a right-linear system of regular recursion equations that defines the language accepted by m.


See Also

RegExp, Fm, RegEqnsFm, ppRegEqnsFm

Discussion

A function translating a right- or left-linear recursion equation system to a finite automaton would allow to regard equations of the form x.i = x.j + ... as epsilon-transitions in automata.