Re: Regexps from DFA (Zvi Lamm)
7 Feb 1997 23:35:31 -0500

          From comp.compilers

Related articles
Regexps from DFA (G Venkatesha Murthy) (1997-02-02)
Re: Regexps from DFA (1997-02-03)
Re: Regexps from DFA (1997-02-03)
Re: Regexps from DFA (1997-02-07)
Re: Regexps from DFA (1997-02-07)
Re: Regexps from DFA (Philip Lijnzaad) (1997-02-07)
| List of all articles for this month |

From: (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 ( 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

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.