Sun, 21 Oct 2007 19:31:34 -0400

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: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | Sun, 21 Oct 2007 19:31:34 -0400 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 07-10-063 |

Keywords: | lex, theory |

haberg@math.su.se (Hans Aberg) writes:

*> Can the intersection of two regular expression languages be*

*> constructed as a regular expression language?*

I'm going to say something which I hope isn't stupid in response to

this. The class of regular languages forms a Boolean algebra with

respect to the union and intersection operators, which I believe means

that they also form a field with those operators, which means they are

closed with respect to both of them. I believe one can even use the

class of regular languages as a topology.

So, in case, this is a homework problem (since it is a commonly asked

hw problem in automata theory). Identify what the identity languages

are for the two operators. Show that idempotence holds. Find the

union and intersection inverses of a given language. Is there

something interesting about the two inverses? Does DeMorgan's theorem

hold?

Hope this helps,

-Chris

*****************************************************************************

Chris Clark Internet : compres@world.std.com

Compiler Resources, Inc. Web Site : http://world.std.com/~compres

23 Bailey Rd voice : (508) 435-5016

Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.