Re: Intersection of regular expression languages

haberg@math.su.se (Hans Aberg)
Mon, 22 Oct 2007 08:59:41 GMT

          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: haberg@math.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: Mon, 22 Oct 2007 08:59:41 GMT
Organization: Virgo Supercluster
References: 07-10-063 07-10-069
Keywords: lex, theory

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


Post a followup to this message

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