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

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 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 84.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

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 (50 chapters)

  1. Front Matter

    Pages i-xiii
    PDF

  2. Lectures

    1. Front Matter

      Pages 1-1
      PDF

    2. Course Roadmap and Historical Perspective

      • Dexter C. Kozen
      Pages 3-6

    3. Strings and Sets

      • Dexter C. Kozen
      Pages 7-13

    4. Finite Automata and Regular Sets

      • Dexter C. Kozen
      Pages 14-18

    5. More on Regular Sets

      • Dexter C. Kozen
      Pages 19-24

    6. Nondeterministic Finite Automata

      • Dexter C. Kozen
      Pages 25-31

    7. The Subset Construction

      • Dexter C. Kozen
      Pages 32-39

    8. Pattern Matching

      • Dexter C. Kozen
      Pages 40-43

    9. Pattern Matching and Regular Expressions

      • Dexter C. Kozen
      Pages 44-48

    10. Regular Expressions and Finite Automata

      • Dexter C. Kozen
      Pages 49-54

    11. Kleene Algebra and Regular Expressions

      • Dexter C. Kozen
      Pages 55-60

    12. Homomorphisms

      • Dexter C. Kozen
      Pages 61-66

    13. Limitations of Finite Automata

      • Dexter C. Kozen
      Pages 67-71

    14. Using the Pumping Lemma

      • Dexter C. Kozen
      Pages 72-76

    15. DFA State Minimization

      • Dexter C. Kozen
      Pages 77-83

    16. A Minimization Algorithm

      • Dexter C. Kozen
      Pages 84-88

    17. Myhill—Nerode Relations

      • Dexter C. Kozen
      Pages 89-94

    18. The Myhill—Nerode Theorem

      • Dexter C. Kozen
      Pages 95-99

    19. Collapsing Nondeterministic Automata

      • Dexter C. Kozen
      Pages 100-107
Back to top

About this book

The aim of this textbook is to provide undergraduate students with an introduction to the basic theoretical models of computability, and to develop some of the model's rich and varied structure. Students who have already some experience with elementary discrete mathematics will find this a well-paced first course, and a number of supplementary chapters introduce more advanced concepts. The first part of the book is devoted to finite automata and their properties. Pushdown automata provide a broader class of models and enable the analysis of context-free languages. In the remaining chapters, Turing machines are introduced and the book culminates in discussions of effective computability, decidability, and Gödel's incompleteness theorems. Plenty of exercises are provided, ranging from the easy to the challenging. As a result, this text will make an ideal first course for students of computer science.
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 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 84.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Search

Navigation