From: Edward Faulkner <ef@...>
Date: 2005-12-13T05:51:22+09:00
Subject: Re: matches -> regexp ?

--o0ZfoUVt4BxPQnbU
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

> ako... schrieb:
> >does anyone know of any reference or an algorithm to build a regular
> >expression (a finite automaton, in general) that would match a given
> >set of strings? i of course mean a regexp that would match just the
> >given strings, and not any other. so solutions like /^.*$/ are not
> >acceptable ;-)

This is essentially an information compression problem.  There's
always a trivial solution:

s = %w{find only these strings}
r = Regexp.new(s.map {|w| '\A' + w + '\Z'}.join('|'))

The _real_ problem is finding the shortest possible regexp. ;-)

--o0ZfoUVt4BxPQnbU
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD4DBQFDneKDnhUz11p9MSARAhZdAJikR9LxgvRKe+HQx+NM/iFPTQPDAKCg7yyF
k9ZvZV/M0aud/vCU9NxSLw==
=EgnI
-----END PGP SIGNATURE-----

--o0ZfoUVt4BxPQnbU--