Mon, 22 Oct 2007 08:59:41 GMT

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

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.