The REGEXP_WEAK signature

Synopsis

signature REGEXP_WEAK


This signature omits a few values from the signature REGEXP for the RegExp structure. (not stable)

Interface

datatype
  'a
  re
  = Atom of 'a| Plus of 'a re list| Star of 'a re| Times of 'a re list| Var of int
val Unit : 'a re
val Zero : 'a re
val It : 'a re -> 'a re
val Power : 'a re -> int -> 'a re
val Powers : 'a re -> int -> 'a re
exception Undefined
val nf : ''a re -> ''a re
val dnf : ''a re -> ''a re
val factorizel : ''a re -> ''a re
val factorizer : ''a re -> ''a re


Description

datatype
  'a
  re
  = Atom of 'a| Plus of 'a re list| Star of 'a re| Times of 'a re list| Var of int


the type of regular expressions over an alphabet of type 'a.

Unit

expression for the neutral element of Times

Zero

expression for the neutral element of Plus

It r

expression for a product of at least one factors r

Power re i

expression for a product of i many factors r

Powers r i

expression for the sum of all powers of r with at most i factors r

exception Undefined


nf r

returns a (quasi) normal form of r, using idempotency of Plus, associativity of Plus and Times, neutrality of Zero and Unit, annihilation by Zero, reflexivity and transitivity of Star, i.e. (x* + y + 1)* = (x + y)*, and 1* = 1 = 0*.

dnf r

returns a distributive normal form of r. Subexpressions of the form (Star s) remain unchanged

factorizel r

returns a left factorization of r, if this is a Plus of expressions, otherwise returns r. A left factorization of Plus rs extracts common left factors of summands in rs, using distribution laws.

factorizer r

returns a right factorization of r, if this is a Plus of expressions, otherwise returns r.

See Also

RegExp, ppRegExp