Sun, 3 Jan 2010 13:06:51 -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) |

Re: How to compute a regex which is the difference between two regexes kkylheku@gmail.com (Kaz Kylheku) (2010-01-06) |

[1 later articles] |

From: | Michiel <mhelvens@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Sun, 3 Jan 2010 13:06:51 -0800 (PST) |

Organization: | Compilers Central |

References: | 10-01-013 |

Keywords: | lex |

Posted-Date: | 04 Jan 2010 11:15:24 EST |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.