Introduction to Automata Theory, Languages, and Computation

Front Cover
It has been more than 20 years since this classic book on formal languages, automata theory, and computational complexity was first published. With this long-awaited revision, the authors continue to present the theory in a concise and straightforward manner, now with an eye out for the practical applications. They have revised this book to make it more accessible to today's students, including the addition of more material on writing proofs, more figures and pictures to convey ideas, side-boxes to highlight other interesting material, and a less formal writing style. Exercises at the end of each chapter, including some new, easier exercises, help readers confirm and enhance their understanding of the material. *NEW! Completely rewritten to be less formal, providing more accessibility to todays students. *NEW! Increased usage of figures and pictures to help convey ideas. *NEW! More detail and intuition provided for definitions and proofs. *NEW! Provides special side-boxes to present supplemental material that may be of interest to readers. *NEW! Includes more exercises, including many at a lower level. *NEW! Presents program-like notation for PDAs and Turing machines. *NEW! Increas

From inside the book

What people are saying - Write a review

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


The Methods and the Madness
Finite Automata
Regular Expressions and Languages

9 other sections not shown

Other editions - View all

Common terms and phrases

About the author (2001)

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

Bibliographic information