Skip to main content
SpringerLink
Log in
Book cover

Automata and Computability

  • Textbook
  • © 1977
Download book PDF

Overview

Authors:
  1. Dexter C. Kozen

    1. Department of Computer Science, Cornell University, Ithaca, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: Undergraduate Texts in Computer Science (UTCS)

Buy print copy

Table of contents (67 chapters)

  1. Front Matter

    Pages i-xiii
    Download chapter PDF

  2. Lectures

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Introduction

      1. Course Roadmap and Historical Perspective
        • Dexter C. Kozen
        Pages 3-6
        Download chapter PDF
      2. Strings and Sets
        • Dexter C. Kozen
        Pages 7-13
        Download chapter PDF

    3. Finite Automata and Regular Sets

      1. Finite Automata and Regular Sets
        • Dexter C. Kozen
        Pages 14-18
        Download chapter PDF
      2. More on Regular Sets
        • Dexter C. Kozen
        Pages 19-24
        Download chapter PDF
      3. Nondeterministic Finite Automata
        • Dexter C. Kozen
        Pages 25-31
        Download chapter PDF
      4. The Subset Construction
        • Dexter C. Kozen
        Pages 32-39
        Download chapter PDF
      5. Pattern Matching
        • Dexter C. Kozen
        Pages 40-43
        Download chapter PDF
      6. Pattern Matching and Regular Expressions
        • Dexter C. Kozen
        Pages 44-48
        Download chapter PDF
      7. Regular Expressions and Finite Automata
        • Dexter C. Kozen
        Pages 49-54
        Download chapter PDF
      8. Kleene Algebra and Regular Expressions
        • Dexter C. Kozen
        Pages 55-60
        Download chapter PDF
      9. Homomorphisms
        • Dexter C. Kozen
        Pages 61-66
        Download chapter PDF
      10. Limitations of Finite Automata
        • Dexter C. Kozen
        Pages 67-71
        Download chapter PDF
      11. Using the Pumping Lemma
        • Dexter C. Kozen
        Pages 72-76
        Download chapter PDF
      12. DFA State Minimization
        • Dexter C. Kozen
        Pages 77-83
        Download chapter PDF
      13. A Minimization Algorithm
        • Dexter C. Kozen
        Pages 84-88
        Download chapter PDF
      14. Myhill—Nerode Relations
        • Dexter C. Kozen
        Pages 89-94
        Download chapter PDF
      15. The Myhill—Nerode Theorem
        • Dexter C. Kozen
        Pages 95-99
        Download chapter PDF
      16. Collapsing Nondeterministic Automata
        • Dexter C. Kozen
        Pages 100-107
        Download chapter PDF
Back to top

Keywords

About this book

These are my lecture notes from CS381/481: Automata and Computability Theory, a one-semester senior-level course I have taught at Cornell Uni­ versity for many years. I took this course myself in thc fall of 1974 as a first-year Ph.D. student at Cornell from Juris Hartmanis and have been in love with the subject ever sin,:e. The course is required for computer science majors at Cornell. It exists in two forms: CS481, an honors version; and CS381, a somewhat gentler­ paced version. The syllabus is roughly the same, but CS481 go es deeper into thc subject, covers more material, and is taught at a more abstract level. Students are encouraged to start off in one or the other, then switch within the first few weeks if they find the other version more suitaLle to their level of mathematical skill. The purpose of t.hc course is twofold: to introduce computer science students to the rieh heritage of models and abstractions that have arisen over the years; and to dew!c'p the capacity to form abstractions of their own and reason in terms of them.

Authors and Affiliations

  • Department of Computer Science, Cornell University, Ithaca, USA

    Dexter C. Kozen

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation