Re: Intersection of regular expression languages

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.

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