This study book by Dexter C. Kozen offers undergraduate students a clear introduction to the fundamental theoretical models of computability. With a focus on a systematic build-up, the book covers finite automata, pushdown automata, and context-free languages. The reader is then introduced to Turing machines, effective computability, decidability, and Gödel’s incompleteness theorems.
Description
The book is intended for undergraduate students with a basic knowledge of discrete mathematics and provides an introduction to the main models of computational theory. In addition to detailed explanations, it includes numerous exercises ranging from simple to challenging. The course starts with finite automata and extends to more complex models with pushdown automata. In later chapters, Turing machines and advanced theoretical concepts are covered.
Promotional information
Springer Book Archives
Product specifications
- Author: Dexter C. Kozen
- Series: Undergraduate Texts in Computer Science
- Publisher: Springer-Verlag New York Inc.
- Publication date: 1997-04-30
- Number of pages: 400
- ISBN: 9780387949079
- Subject: Mathematical theory of computation
- BISAC: COMPUTERS / Machine Theory