Sun, 3 Jan 2010 08:20:05 -0800 (PST)

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

[2 later articles] |

From: | Peng Yu <pengyu.ut@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Sun, 3 Jan 2010 08:20:05 -0800 (PST) |

Organization: | Compilers Central |

Keywords: | lex, theory |

Posted-Date: | 03 Jan 2010 14:45:22 EST |

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?

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.