Automata And Computability by Dexter Kozen (1997)

This textbook aims to offer undergraduate students an introduction to the fundamental theoretical models of computability, delving into the diverse and intricate structure of these models. It caters to students with some background in elementary discrete mathematics, presenting a well-paced initial course with additional chapters introducing more advanced concepts.

cover

The first section of the book focuses on finite automata and their characteristics, while pushdown automata extend the scope to analyze context-free languages. The subsequent chapters introduce Turing machines, leading to discussions on effective computability, decidability, and Gödel’s incompleteness theorems. The book provides a range of exercises, from straightforward to challenging, making it an ideal first course for computer science students.

Download

Ebook


See also