7 Feb 1997 23:35:31 -0500

Related articles |
---|

Regexps from DFA gvmt@csa.iisc.ernet.in (G Venkatesha Murthy) (1997-02-02) |

Re: Regexps from DFA anton@a0.complang.tuwien.ac.at (1997-02-03) |

Re: Regexps from DFA dimock@deas.harvard.edu (1997-02-03) |

Re: Regexps from DFA clark@quarry.zk3.dec.com (1997-02-07) |

Re: Regexps from DFA mslamm@pluto.mscc.huji.ac.il (1997-02-07) |

Re: Regexps from DFA lijnzaad@ebi.ac.uk (Philip Lijnzaad) (1997-02-07) |

From: | mslamm@pluto.mscc.huji.ac.il (Zvi Lamm) |

Newsgroups: | comp.compilers |

Date: | 7 Feb 1997 23:35:31 -0500 |

Organization: | Hebrew University, Jeruslem, Israel |

References: | 97-02-020 97-02-028 |

Keywords: | lex, DFA |

Anton Ertl (anton@a0.complang.tuwien.ac.at) wrote:

*: Perhaps what you are searching for would be accomplished by a tool*

*: like this: Given a set of example strings that are in your language*

*: ("in"), and a set of strings that are not in your language ("out"),*

*: return the simplest RE (according to some metric, e.g., number of RE*

*: operators) for a language that is a superset of the "in" set, and*

*: disjoint from the "out" set.*

This reminds me of question 3.36 in the Red Dragon:

Give an algorithm that takes as an input a string x and a regex r, and

produces as output a string y in L(r), such that d(x,y) (this is the

minimal edit distance, E.L) is a small as possible.

The refernce is to Wagner R. A. "Order-n correction fo regular languages"

CACM 16:5, 1974.

Hope this helps,

--

Ehud Lamm mslamm@pluto.mscc.huji.ac.il

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.