• Arnold L. Rosenberg
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)


The notion of state is fundamental to the design and analysis of virtually all computational systems. The Myhill-Nerode Theorem of Finite Automata theory—and the concepts underlying the Theorem—is a source of sophisticated fundamental insights about a large class of state-based systems, both finite-state and infinite-state systems. The Theorem’s elegant algebraic characterization of the notion of state often allows one to analyze the behaviors and resource requirements of such systems. This paper reviews the Theorem and illustrates its application to a variety of formal computational systems and problems, ranging from the design of circuits, to the analysis of data structures, to the study of state-based formalisms for machine-learning systems. It is hoped that this survey will awaken many to, and remind others of, the importance of the Theorem and its fundamental insights.


Equivalence Relation Input Port Regular Language Finite Automaton Input String 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. 1.
    Hartmanis, J., Stearns, R.E.: Algebraic Structure Theory of Sequential Machines. Prentice Hall, Englewood Cliffs (1966)zbMATHGoogle Scholar
  2. 2.
    Hennie, F.C.: On-line Turing machine computations. IEEE Trans. Electronic Computers EC-15, 35–44 (1966)CrossRefGoogle Scholar
  3. 3.
    Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Reading (2001)zbMATHGoogle Scholar
  4. 4.
    Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 1st edn. Addison-Wesley, Reading (1979)zbMATHGoogle Scholar
  5. 5.
    Jaffe, J.: A necessary and sufficient pumping lemma for regular languages. SIGACT News, 48–49 (1978)Google Scholar
  6. 6.
    Karp, R.M.: Some bounds on the storage requirements of sequential machines and Turing machines. J. ACM 14, 478–489 (1967)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Knuth, D.E.: The Art of Computer Programming: Fundamental Algorithms, 2nd edn. Addison-Wesley, Reading (1973)Google Scholar
  8. 8.
    Lewis, H.R., Papadimitriou, C.H.: Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs (1981)zbMATHGoogle Scholar
  9. 9.
    Linz, P.: An Introduction to Formal Languages and Automata, 3rd edn. Jones and Bartlett Publ. Sudbury (2001)Google Scholar
  10. 10.
    Moore, E.F.: Gendanken experiments on sequential machines. In: Shannon, C.E., McCarthy, J. (eds.) [Ann. Math. Studies 34], Automata Studies, pp. 129–153. Princeton Univ. Press, Princeton (1956)Google Scholar
  11. 11.
    Moret, B.M.: The Theory of Computation. Addison-Wesley, Reading (1997)Google Scholar
  12. 12.
    Myhill, J.:: Finite automata and the representation of events. WADD TR- 57-624, Wright Patterson AFB, Ohio, pp. 112–137 (1957)Google Scholar
  13. 13.
    Nerode, A.: Linear automaton transformations. In: Proc. AMS, vol. 9, pp. 541–544 (1958)Google Scholar
  14. 14.
    Rabin, M.O.: Probabilistic automata. Inform. Control 6, 230–245 (1963)CrossRefGoogle Scholar
  15. 15.
    Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Develop. 3, 114–125 (1959)CrossRefMathSciNetGoogle Scholar
  16. 16.
    Rosenberg, A.L.: Data graphs and addressing schemes. J. CSS 5, 193–238 (1971)zbMATHGoogle Scholar
  17. 17.
    Schönhage, A.: Storage modification machines. SIAM J. Computing 9, 490–508 (1980)zbMATHCrossRefGoogle Scholar
  18. 18.
    Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Co., Boston (1997)zbMATHGoogle Scholar
  19. 19.
    Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. 42(2), 230–265 (1936); Correction ibid., vol. 43, 544–546Google Scholar
  20. 20.
    Wikipedia: The Free Encyclopedia (2005),

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Arnold L. Rosenberg
    • 1
  1. 1.Dept. of Computer ScienceUniversity of MassachusettsAmherstUSA

Personalised recommendations