16 May 1999 15:35:00 -0400

Related articles |
---|

Book Recommendation: Automata and Computability mcr@visi.com (Michael Roach) (1999-05-16) |

From: | Michael Roach <mcr@visi.com> |

Newsgroups: | comp.compilers |

Date: | 16 May 1999 15:35:00 -0400 |

Organization: | Compilers Central |

Keywords: | books |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.