Introduction to Automata Theory, Languages, and Computation

Front Cover
Addison-Wesley, 1979 - Computational complexity - 418 pages
12 Reviews
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.

From inside the book

What people are saying - Write a review

User ratings

5 stars
4 stars
3 stars
2 stars
1 star

LibraryThing Review

User 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 Review

User 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


Finite Automata and Regular Expressions
Properties of Regular Sets

13 other sections not shown

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »

About the author (1979)

Ullman is the Stanford W. Ascherman Professor of Computer Science at Stanford.

Bibliographic information