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

Peng Yu <pengyu.ut@gmail.com> writes:


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


I don't have the Hopcroft, Motwani, and Ullman book in front of me,
but from the table of contents, it looks like you are in the wrong
section. You want section 4.2.1 (Closure of Regular Languages uUnder
Boolean Operations) together with section 3.2 (Finite Automata and
Regular Expressions) and section 2.3.5 (Equivalence of Deterministic
and Nondeterministic Finite Automata).


Section 4.2.1 would be enough to answer in the affirmative your
question of existence; the difference of two regular sets is itself
regular. However, I would bet it shows this using a construction on
automata rather than regular expressions. Thus, to answer your
further question ("a mechanical way to generate such regular
expression"), you would need the techniques in section 3.2 for
converting back and forth between regular expressions and automata, as
well (probably) as the technique in section 2.3.5 for converting from
a nondeterministic automaton to a deterministic one. If I am guessing
correctly the contents of this book, a sketch of the overall algorithm
would look like this:


    Convert the input languages A and B from REs to NFAs (section 3.2.3)
    Construct the NFA for the set difference (section 4.2.1)
    Convert that NFA into a DFA (section 2.3.5)
    Convert the DFA into an RE (sections 3.2.1-3.2.2)


Regarding the core of the matter (constructing the set difference)
this may well not be explicit in section 4.2.1. Typical textbooks
instead show the constructions for intersection and complement. But
A-B is the same as A intersected with the complement of B.

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