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

## Michiel <mhelvens@gmail.com>Sun, 3 Jan 2010 13:06:51 -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)
[1 later articles]
| List of all articles for this month |

 From: Michiel Newsgroups: comp.compilers Date: Sun, 3 Jan 2010 13:06:51 -0800 (PST) Organization: Compilers Central References: 10-01-013 Keywords: lex Posted-Date: 04 Jan 2010 11:15:24 EST

Peng Yu wrote:

> Could somebody show me how to
> compute the regular expression for the difference between two regular
> sets, given the two original regular expressions?

Yes, regular languages are closed under the difference operation.

I haven't worked with them a lot lately, but I learned the following
way to derive the difference (intersection, union, ...) of two regexes
in a mechanic (if complex) way:

* Translate the regular expressions A, B into deterministic finite
automata
fA, fB. There is an algorithm for this.
* The finite automaton fC contains the Cartesian product of the states
in fA
and fB and contains the transition x:(a*b, c*d) if fA contains x:(a,
c) and
fB contains x:(b, d).
* In fC, a*b is the initial state iff a is initial in fA and b is
initial in
fB.
* In fC, state a*b is a final state iff:
- a is final in fA and b is not final in fB: difference (!)
- a is final in fA and b is final in fB: intersection
- a is final in fA or b is final in fB: union
- ...
* Remove unreachable states from fC.
* Translate deterministic finite automaton fC into a regular
expression C.
There is an algorithm for this.

There may be a faster way.

Good luck,

--
Michiel Helvensteijn

Post a followup to this message