Re: Regexps from DFA

mslamm@pluto.mscc.huji.ac.il (Zvi Lamm)
7 Feb 1997 23:35:31 -0500

          From comp.compilers
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)
| List of all articles for this month |
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.