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  <cai@nimari.nmrfam.wisc.edu> 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