Skip to main content
SpringerLink
Log in
Book cover
  • Textbook
  • © 1977

Automata and Computability

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)

Sections

Buy it now

eBook USD 74.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (67 chapters)

  1. Front Matter

    Pages i-xiii
    PDF

  2. Lectures

    1. Front Matter

      Pages 1-1
      PDF

    2. Introduction

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

    3. Finite Automata and Regular Sets

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

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.
Back to top

Keywords

Back to top

Authors and Affiliations

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

    Dexter C. Kozen

Back to top

Bibliographic Information

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

eBook USD 74.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Other ways to access

Search

Navigation