re: Regexps from DFA

Jean Mehat <>
3 Feb 1997 13:44:21 -0500

          From comp.compilers

Related articles
re: Regexps from DFA (Jean Mehat) (1997-02-03)
Re: Regexps from DFA (1997-02-07)
| List of all articles for this month |

From: Jean Mehat <>
Newsgroups: comp.compilers
Date: 3 Feb 1997 13:44:21 -0500
Organization: Compilers Central
Keywords: lex
Reference: 97-02-020

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,, (1) 49 40 64 03, (1) 49 40 67 83 (fax)

Post a followup to this message

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