Re: Intersection of regular expression languages

Gene <gene.ressler@gmail.com> 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.


There are regular or Chomsky hierarchy type 3 grammars, and the
languages they produce, I gather are called regular languages.


But a regular expression algebra is just a language expressing some of
the language set and monoid operations:


If C is a character set, let C* denote the free monoid (set of finite
strings), then a regular expression language has symbols for elements
in C, the union, monoid unit and multiplication (concatenation), and
the submonoid generated by a set (Kleene closure).


I was not sure how that related to 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?


Yes. As the language complement can be constructed on the DFA level,
de Morgan shows the intersection can be constructed as well. I
wondered if there was a more direct construction.


> 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.


So that would do it. Thanks.


    Hans Aberg

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