A solution to an open problem by Knuth
David Pager · ACM SIGACT News · 1970
In Knuth [2] the problem of minimizing the number of sets of states required for his parsing algorithm is raised as an open question. We solve this problem by showing it is equivalent to that of finding the minimal representation for an incompletely specified finite automaton. A solution may thus be obtained using the known methods of the latter. This result may be viewed in contrast to Pager [8] and [9] where it is shown that it is not generally possible to make optimizations of this kind.