Re: How to compute a regex which is the difference between two regexes?

Marcin Ciura <mciura@gmail.com>
Mon, 4 Jan 2010 06:26:06 -0800 (PST)

          From comp.compilers
Related articles
How to compute a regex which is the difference between two regexes? pengyu.ut@gmail.com (Peng Yu) (2010-01-03)
Re: How to compute a regex which is the difference between two regexes mhelvens@gmail.com (Michiel) (2010-01-03)
Re: How to compute a regex which is the difference between two regexes egagnon@j-meg.com (Etienne M. Gagnon) (2010-01-03)
Re: How to compute a regex which is the difference between two regexes gene.ressler@gmail.com (Gene) (2010-01-03)
Re: How to compute a regex which is the difference between two regexes mciura@gmail.com (Marcin Ciura) (2010-01-04)
Re: How to compute a regex which is the difference between two regexes max@gustavus.edu (Max Hailperin) (2010-01-04)
Re: How to compute a regex which is the difference between two regexes kkylheku@gmail.com (Kaz Kylheku) (2010-01-05)
Re: How to compute a regex which is the difference between two regexes kkylheku@gmail.com (Kaz Kylheku) (2010-01-06)
Re: How to compute a regex which is the difference between two regexes cfc@shell01.TheWorld.com (Chris F Clark) (2010-01-11)
| List of all articles for this month |
From: Marcin Ciura <mciura@gmail.com>
Newsgroups: comp.compilers
Date: Mon, 4 Jan 2010 06:26:06 -0800 (PST)
Organization: Compilers Central
References: 10-01-013
Keywords: lex, DFA
Posted-Date: 04 Jan 2010 11:27:49 EST

On Jan 3, 5:20 pm, Peng Yu <pengyu...@gmail.com> wrote:
> Suppose that I have two regular sets A and B that are generated by two
> regular expressions. I'm wondering if there is always a regular
> expression that can generated the difference between the two sets,
> i.e., A-B. If there is such regular expression, is there a mechanical
> way to generated such regular expression.
>
> http://www.pearsonhighered.com/educator/academic/product/0,1144,03214...
>
> I looked through Section 3.4 Algebraic laws for regular expressions of
> Introduction to Automata Theory, Languages, and Computation, by
> Hopcroft, Motwani and Ullman (2nd edition). But I don't see the set
> difference between two regular sets. Could somebody show me how to
> compute the regular expression for the difference between two regular
> sets, given the two original regular expressions?
> [It is my strong recollection that the difference of two REs is not
> necessarily a RE, but I can't find the reference for it,
> either. -John]


You can construct a set difference from intersection and
complementation: R \ S = R & ~S.
http://wiki.tcl.tk/461 explains how to build DFAs for the intersection/
complement of regular languages.
Then you can reverse engineer an RE from the DFA if need be.
--
Marcin


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.