| > Read Engineering a Compiler by Cooper and Torczon. That book has an error in it which I have reported to the authors twice but never heard anything back. This leaves a bad taste in my mouth. Here's what I wrote to them: Subject: Errata for "Engineering a Compiler"
Date: Sat, May 26, 2007 at 8:12 PM Hello, I noticed that your section on DFA minimization is labeled "Hopcroft's Algorithm," but doesn't seem to describe the algorithm explained by Hopcroft in his 1971 paper [0]. Your algorithm appears to be n^2, where Hopcroft's is n log n. David Gries gave a somewhat more digestible presentation of the same algorithm in a follow-up paper in 1972 [1]. Hope this information is useful! Sincerely,
<me> [0] John E. Hopcroft. An n log n algorithm for minimizing states in a finite automaton. Technical Report: CS-TR-71-190, 1971. Available online at ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf [1] David Gries. Describing an algorithm by Hopcroft. Acta Informatica, 2(2):97-109. Online reference: http://www.springerlink.com/content/r5631549671g6251/ |