# Re: Intersection of regular expression languages

## Chris F Clark <cfc@shell01.TheWorld.com>Sun, 21 Oct 2007 19:31:34 -0400

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: Chris F Clark 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 Posted-Date: 22 Oct 2007 00:23:37 EDT

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