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

## Marcin Ciura <mciura@gmail.com>

Mon, 4 Jan 2010 06:26:06 -0800 (PST)

*From comp.compilers*

| List of all articles for this month |

**From: ** | Marcin Ciura <mciura@gmail.com> |

**Newsgroups: ** | comp.compilers |

**Date: ** | Mon, 4 Jan 2010 06:26:06 -0800 (PST) |

**Organization: ** | Compilers Central |

**References: ** | 10-01-013 |

**Keywords: ** | lex, DFA |

**Posted-Date: ** | 04 Jan 2010 11:27:49 EST |

On Jan 3, 5:20 pm, Peng Yu <pengyu...@gmail.com> wrote:

*> 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,03214...*

*>*

*> 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]*

You can construct a set difference from intersection and

complementation: R \ S = R & ~S.

http://wiki.tcl.tk/461 explains how to build DFAs for the intersection/

complement of regular languages.

Then you can reverse engineer an RE from the DFA if need be.

--

Marcin

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.