From: fateman@peoplesparc.cs.berkeley.edu (Richard J. Fateman)
Subject: Re: help: algorithm for intersection of regular expressions
Date: 10 Jun 1999 18:32:01 GMT
Newsgroups: sci.math.symbolic
In article <375FE66E.14485DC0@nimari.nmrfam.wisc.edu>,
Shangchun Cai wrote:
>I have to find an algorithm to perform the intersection(or
>complementation) of two regular expressions. I know there is a way to
>perform it going through finite automata. However I want to implement it
>directly if it is possible. I am very appreciated if you can give me the
>solution or some references.
>--
>cai@nimari.nmrfam.wisc.edu
You might find this paper and its references useful for algorithms
on REs not using FAs.
J. A. Brzozowski
"Derivatives of Regular Expressions"
J. Assoc. Comp. Mach.
Vol. 11, No. 4, pp. 481-494, October 1964
--
Richard J. Fateman
fateman@cs.berkeley.edu http://http.cs.berkeley.edu/~fateman/
==============================================================================
30 #4638 94.40
Brzozowski, Janusz A.
Derivatives of regular expressions.
J. Assoc. Comput. Mach. 11 1964 481--494.
$N\sb k$ is the set of words over $\{1,\cdots,k\}$, including the
empty word $\lambda$; ${E}\sb k$ is the set of extended regular
expressions (including, as operation symbols, any collection of
boolean functions, in addition to the usual operation symbols $\cup$,
$\cdot$, ${}\sp *$) and $\vert E\vert $ is the set denoted by $E\in{E}\sb
k$. For $w\in N\sb k$ and $\alpha\subseteq N\sb k$, the derivative of
$\alpha$ with respect to $w$ is defined by $D\sb w\alpha=\{u\vert
wu\in\alpha\}$.
Although not specifically noted by the author, the derivatives of
$\alpha$ are in one-one correspondence with the classes of $\pi\sb
\alpha$, the induced right congruence relation of $\alpha$ (the
congruence relation associated with the minimal state automaton
recognizing $\alpha$) i.e., $D\sb {w\sb 1}\alpha=D\sb {w\sb 2}\alpha$
if and only if $w\sb 1\pi\sb \alpha w\sb 2$. Several properties of
derivatives are proved, all of which follow immediately from this
observation. The contribution of the paper comes from the author's
treatment of regular expressions. The first relevant theorem provides
an inductive definition of a function ${D}\sb w$ on ${E}\sb k$ such
that $\vert {D}\sb wE\vert =D\sb w\vert E\vert $. Write $E\sb 1\sim
E\sb 2$ if and only if $E\sb 1=E\sb 2$ can be equationally deduced
from the idempotent, commutative and associative identities of $\cup$.
The main new result is that the relation $w\sb 1\sim w\sb 2(E)$,
defined by ${D}\sb {w\sb 1}E\sim{D}\sb {w\sb 2}E$, has finite index.
With this result, the author describes an algorithm for obtaining a
finite automaton $A$ (in general, not minimal) with behavior $\vert
E\vert $, by taking successive derivatives of $E$ and applying only
the simple laws for $\cup$ to test for the termination of the process.
Reviewed by J. W. Thatcher
_________________________________________________________________
26 #3552 94.30
Brzozowski, Janusz A.
A survey of regular expressions and their applications.
IRE Trans. EC-11 1962 324--335.
Author's summary: "This paper is an exposition of the theory of
regular expressions and its applications to sequential circuits. The
results of several authors are presented in a unified manner, pointing
out the similarities and differences in the various treatments of the
subject. Whenever possible, the terminology and notation of sequential
circuit theory are used. The topics presented include: the relation of
regular expressions to sequential circuits; algorithms for
constructing sequential circuits and state diagrams corresponding to a
given regular expression; methods for obtaining a regular expression
from a state diagram of a sequential circuit, improper state diagrams,
algebraic properties of regular expressions, and applications to
codes."
(c) Copyright American Mathematical Society 2000