re: Regexps from DFA

G V Murthy:
> what regexp would describe a given set of strings.


Mod:
> 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
useful.


--
Jean Mehat, universite de Paris 8 Vincennes a Saint Denis,
jm@univ-paris8.fr, (1) 49 40 64 03, (1) 49 40 67 83 (fax)
--

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