|Regexps from DFA email@example.com (G Venkatesha Murthy) (1997-02-02)|
|Re: Regexps from DFA firstname.lastname@example.org (1997-02-03)|
|Re: Regexps from DFA email@example.com (1997-02-03)|
|Re: Regexps from DFA firstname.lastname@example.org (1997-02-07)|
|Re: Regexps from DFA email@example.com (1997-02-07)|
|Re: Regexps from DFA firstname.lastname@example.org (Philip Lijnzaad) (1997-02-07)|
|From:||email@example.com (Zvi Lamm)|
|Date:||7 Feb 1997 23:35:31 -0500|
|Organization:||Hebrew University, Jeruslem, Israel|
Anton Ertl (firstname.lastname@example.org) 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 email@example.com
Return to the
Search the comp.compilers archives again.