Mon, 04 Jan 2010 08:48:43 -0600

From: | Max Hailperin <max@gustavus.edu> |

Newsgroups: | comp.compilers |

Date: | Mon, 04 Jan 2010 08:48:43 -0600 |

Organization: | Compilers Central |

References: | 10-01-013 |

Keywords: | lex, DFA |

Posted-Date: | 04 Jan 2010 11:28:01 EST |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.