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

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

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