Introduction to Automata Theory, Languages, and Computation
Addison-Wesley, 1979 - Computational Complexity - 418 pages
Preliminaries. Finite automata and regular expressions. Properties of regular sets. Context-free grammars. Pushdown automata; Properties of context-free languages. Turing machines. Undecidability. The Cohmsky hierarchy. Heterministic context-free languages. Closure properties of families of languages. Computational complexity theory. Intractable problems. Highlights of other important language classes.
What people are saying - Write a review
LibraryThing ReviewUser Review - Foretopman - LibraryThing
I need to make it clear right at the beginning that this is a review of the first (1979) edition of this book. It's my understanding that the second edition is better. I knew that this book was going ... Read full review
LibraryThing ReviewUser Review - dominus - LibraryThing
(This is a review of the first edition of this book.) This is another one of those rotten books that is difficult to read even when you already know the subject matter backward and forward. One of the ... Read full review