Sun, 21 Oct 2007 16:42:57 -0700

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

Newsgroups: | comp.compilers |

Date: | Sun, 21 Oct 2007 16:42:57 -0700 |

Organization: | Compilers Central |

References: | 07-10-063 |

Keywords: | lex, theory |

Posted-Date: | 22 Oct 2007 00:23:57 EDT |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.