Re: Regexps from DFA

anton@a0.complang.tuwien.ac.at (Anton Ertl)
3 Feb 1997 13:41:35 -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: anton@a0.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Date: 3 Feb 1997 13:41:35 -0500
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 97-02-020
Keywords: lex

G Venkatesha Murthy <gvmt@csa.iisc.ernet.in> writes:
> We recently had a post asking what regexp would describe a given set
> of strings.


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.


It should be possible to find a solution in finite time by enumerating
all REs, starting with the simplest, but this method may take too long
to be practical for interesting REs.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html
--

Post a followup to this message

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