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