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

Peng Yu <pengyu.ut@gmail.com>
Sun, 3 Jan 2010 08:20:05 -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)
[2 later articles]
| List of all articles for this month |
From: Peng Yu <pengyu.ut@gmail.com>
Newsgroups: comp.compilers
Date: Sun, 3 Jan 2010 08:20:05 -0800 (PST)
Organization: Compilers Central
Keywords: lex, theory
Posted-Date: 03 Jan 2010 14:45:22 EST

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,0321462254,00.html


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]


Post a followup to this message

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