Automata and Computability

by Dexter C. Kozen

This textbook provides undergraduate students with an introduction to the basic theoretical models of computability, and develops some of the model's rich and varied structure. 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 analyses of effective computability, decidability, and Gödel's incompleteness theorems. Students who already have some experience with elementary discrete mathematics will find this a well-paced first course, and a number of supplementary chapters introduce more advanced concepts.

Genres: Computer Science, Reference, Mathematics, Programming, Nonfiction

413 pages, Hardcover

First published August 1, 1997

Reviews

[jac · Rating 5 out of 5]

Incredibly, concise without being opaque. Few-page chapters/lectures that have everything you need and nothing more. I highly recommend this book as a practical introduction.

[Laura Zielinski · Rating 5 out of 5]

Beautifully-written and gives a thorough and precise treatment of formal languages, finite automata, and models of computation. The first textbook that I have finished cover to cover. As readable as a novel. It is fascinating to read and perfectly-paced for a student, yet writes with utmost clarity, concision, and rigor. There is not a sentence that I have any confusion or doubts about. Anyone who calls themselves a computer scientist must read this book.