Book Recommendation: Automata and Computability

I just had to post a recommendation for a book I have been reading as
of late. It's called Automata and Computability by Dexter C. Kozen, and
its ISBN # 0-387-94907-0. It looks to be a first edition printing.


The book consists of the author's lecture notes from a 1 semester
senior-level course he taught at Cornell Univeristy entiled: Automata
and Computability Theory. I have been teaching myself automata and set
theory for several years now, but have constantly found myself
struggling with even the simplest of problems. This books has answered
my questions, and for once I feel confident reading some of the more
abstract papers that abound on the subject. It's written very plainly,
with enough proofs to show how and why things work, but it doesn't
over do it like so many other texts do.


If your having difficulty understanding DFAs, NFAs, CFGs, etc and their
construction along with the theory that makes it all happen, then this
is a book to read. It does require a bit of mathematical sophistication,
but not much, and where it is needed the book provides alot of help.


Another plus is its really cheap (to me anyways) and costs roughly $39 US
through Barnes and Noble. Maybe now I'll actually be able to contribute
to this wonderful newsgroup rather than constantly asking questions :)




Table of Contents
Contents
Preface
Lectures
Introduction
1 Course Roadmap and Historical Perspective
2 Strings and Sets
Finite Automata and Regular Sets
3 Finite Automata and Regular Sets
4 More on Regular Sets
5 Nondeterministic Finite Automata
6 The Subset Construction
7 Pattern Matching
8 Pattern Matching and Regular Expressions
9 Regular Expressions and Finite Automata
A Kleene Algebra and Regular Expressions
10 Homomorphisms
11 Limitations of Finite Automata
12 Using the Pumping Lemma
13 DFA State Minimization
14 A Minimization Algorithm
15 Myhill–Nerode Relations
16 The Myhill–Nerode Theorem
B Collapsing Nondeterministic Automata
C Automata on Terms
D The Myhill–Nerode Theorem for Term Automata
17 Two‐Way Finite Automata
18 2DFAs and Regular Sets
Pushdown Automata and Context‐Free Languages
19 Context‐Free Grammars and Languages
20 Balanced Parentheses
21 Normal Forms
22 The Pumping Lemma for CFLs
23 Pushdown Automata
E Final State Versus Empty Stack
24 PDAs and CFGs
25 Simulating NPDAs by CFGs
F Deterministic Pushdown Automata
26 Parsing
27 The Cocke–Kasami–Younger Algorithm
G The Chomsky–Sch&uouml;tzenberger Theorem
H Parikh's Theorem
Turing Machines and Effective Computability
28 Turing Machines and Effective Computability
29 More on Turing Machines
30 Equivalent Models
31 Universal Machines and Diagonalization
32 Decidable and Undecidable Problems
33 Reduction
34 Rice's Theorem
35 Undecidable Problems About DFLs
36 Other Formalisms
37 The &lgr;‐Calculus
I While Programs
J Beyond Undecidability
38 Gödel's Incompleteness Theorem
39 Proof of the Incompleteness Theorem
K Gödel's Proof


Exercises
Homework Sets
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Homework 10
Homework 11
Homework 12


Miscellaneous Exercises
Finite Automata and Regular Sets
Pushdown Automata and Context‐Free Languages
Turing Machines and Effective Computability
Hints and Solutions
Hints for Selected Miscellaneous Exercises
Solutions to Selected Miscellaneous Exercises


References
Notations
Index
--
Michael Charles Roach (_)
Saint Paul, MN USA Flying Enthusiast, PP-ASEL
mcr@(tiny|yuck).net Ham Radio Call Sign KB0LXV

Return to the comp.compilers page.
Search the comp.compilers archives again.