Re: Intersection of regular expression languages

Gene <gene.ressler@gmail.com>
Sun, 21 Oct 2007 16:42:57 -0700

          From comp.compilers

Related articles
Intersection of regular expression languages haberg@math.su.se (2007-10-19)
Re: Intersection of regular expression languages neelk@cs.cmu.edu (Neelakantan Krishnaswami) (2007-10-21)
Re: Intersection of regular expression languages cfc@shell01.TheWorld.com (Chris F Clark) (2007-10-21)
Re: Intersection of regular expression languages gene.ressler@gmail.com (Gene) (2007-10-21)
Re: Intersection of regular expression languages wyrmwif@tsoft.org (SM Ryan) (2007-10-21)
Re: Intersection of regular expression languages haberg@math.su.se (2007-10-22)
| List of all articles for this month |

From: Gene <gene.ressler@gmail.com>
Newsgroups: comp.compilers
Date: Sun, 21 Oct 2007 16:42:57 -0700
Organization: Compilers Central
References: 07-10-063
Keywords: lex, theory
Posted-Date: 22 Oct 2007 00:23:57 EDT

On Oct 19, 3:39 pm, haberg@math.su.se (Hans Aberg) wrote:
> Can the intersection of two regular expression languages be
> constructed as a regular expression language?


Sure, but either your terminology is off a little or I'm going to
answer the wrong question. There are regular languages and there are
regular expressions, which are a language to describe regular
languages. So I think you are asking, given two regexes, can you find
a third regex that represents the intersection of the languages
described by the first two?


For this, see just about any textbook on finite automata. Thompson's
construction gets you from regex to NFA. Subset construction gets you
to DFA. There is a standard algorithm for finding a DFA that
recognizes the intersection of languages recognized by two others A
and B. Roughly speaking, you "simulate" A and B running in parallel
with a new DFA C having states labeled by pairs of original states
(something like the subset construction), one from A and one from B.
The accepting states of C are those labeled by two accepting states.
Then there is another standard algorithm to get from a DFA to a
regex. This is often presented as part of the proof of Kleene's
theorem. In practice you'd probably want to minimize the intersection
machine, which is another standard algorithm.


Some of the above steps are given in many compiler textbooks, but not
all.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.