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