|Intersection of regular expression languages email@example.com (2007-10-19)|
|Re: Intersection of regular expression languages firstname.lastname@example.org (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 email@example.com (Gene) (2007-10-21)|
|Re: Intersection of regular expression languages firstname.lastname@example.org (SM Ryan) (2007-10-21)|
|Re: Intersection of regular expression languages email@example.com (2007-10-22)|
|From:||firstname.lastname@example.org (Hans Aberg)|
|Date:||Mon, 22 Oct 2007 08:59:41 GMT|
|Posted-Date:||22 Oct 2007 12:20:59 EDT|
Gene <email@example.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
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.
Return to the
Search the comp.compilers archives again.