|re: Regexps from DFA firstname.lastname@example.org (Jean Mehat) (1997-02-03)|
|Re: Regexps from DFA email@example.com (1997-02-07)|
|From:||Jean Mehat <firstname.lastname@example.org>|
|Date:||3 Feb 1997 13:44:21 -0500|
G V Murthy:
> what regexp would describe a given set of strings.
> I still don't understand the question. RE's are either valid or not,
I once dreamed to have a unix ls command option that would do:
$ ls --regexpr
a.out makefile *.c *.o
$ ls --regexpr2
a.out makefile foo.[co] bar.[co] joe.[co]
It might be expressed as a ``minimal regexpr for a given set of strings''.
I didn't clarify the notion of generality vs. simplicity, as '.*' can match
anything and has a minimal number of states as a DFA, while the exact match
for all strings is minimal in term of size of the generated language.
The interesting expr/automatas are somewhere in between.
What I can say is that an algorithm inspired from the minimal spanning
tree (combine the two simplest automata) doesn't give anything really
Jean Mehat, universite de Paris 8 Vincennes a Saint Denis,
email@example.com, (1) 49 40 64 03, (1) 49 40 67 83 (fax)
Return to the
Search the comp.compilers archives again.