7 Mar 1998 22:33:07 -0500

Related articles |
---|

Regular expressions; cannonical form and reducer? guthrie@mum.edu (1998-03-06) |

Re: Regular expressions; cannonical form and reducer? matkin@iar.se (Mats Kindahl) (1998-03-07) |

Re: Regular expressions; cannonical form and reducer? zss@ZenSpider.com (1998-03-07) |

Re: Regular expressions; cannonical form and reducer? dietz@interaccess.com (Paul Dietz) (1998-03-08) |

Re: Regular expressions; cannonical form and reducer? henry@zoo.toronto.edu (Henry Spencer) (1998-03-08) |

From: | Mats Kindahl <matkin@iar.se> |

Newsgroups: | comp.compilers |

Date: | 7 Mar 1998 22:33:07 -0500 |

Organization: | IAR Systems |

References: | 98-03-034 |

Keywords: | DFA |

Gregory Guthrie wrote:

*>*

*> I am interested in any references to a standard cannonical form for*

*> regular expressions, and any system that would transform Regex into*

*> such forms.*

*>*

*> This would, for example allow one to test equivalence of two Regex*

*> forms.*

*>*

*> Seems like this should either exist, or be impossible. :-)*

It would certainly be possible to construct a canonical form for

regular expressions, but using automata as canonical form would be

more appropriate.

The easiest way would probably be to construct an DFA for the regular

expression and then reduce it using a slightly modified version of

Paige-Tarjan's algorithm to compute a reduced graph with bisimilar

states merged.

Regards,

Mats Kindahl

A reference:

Robert Paige and Robert E. Tarjan.

Three partition refinement algorithms.

SIAM Journal on Computing,

16(6):973-989, December 1987.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.