Catching up from two weeks ago [sorry 'bout that]...
I see there is one thing no-one else mentioned:

Ulrich Hobelmann  <u.hobelmann@web.de> wrote:
+---------------
| 	 (loop with first = (make-instance 'state)
| 	    with nfa = (make-instance 'nfa :start-state first)
| 	    for c in (cons nil (loop for c across string collect c))
|           ...[and the rest]...
+---------------

Yes, I know you later got rid of the CONS and can now use ACROSS
instead of IN, but if for some reason you hadn't done that, you
might be able to get a mild performance improvement by replacing:

	for c in (cons nil (loop for c across string collect c))

with this:

	for c in (cons nil (coerce string 'list)))


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607