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 - <F75BS>NEW! Completely rewritten to be less formal, providing more accessibility to today's students.
- NEW - <F75BS>NEW! Increased usage of figures and pictures to help convey ideas.
- NEW - <F75BS>NEW! More detail and intuition provided for definitions and proofs.
- NEW - <F75BS>NEW! Provides special side-boxes to present supplemental material that may be of interest to readers.
- NEW - <F75BS>NEW! Includes more exercises, including many at a lower level.
- NEW - <F75BS>NEW! Presents program-like notation for PDA's and Turing machines.
- NEW - <F75BS>NEW! Increased number of worked solutions and new programming exercises available online.
Table of Contents
(NOTE: Each chapter concludes with Summary and References.)
1. Automata: The Methods and the Madness.
2. Finite Automata.
3. Regular Expressions and Languages.
4. Properties of Regular Languages.
5. Context-Free Grammars and Languages.
6. Pushdown Automata.
7. Properties of Context-Free Languages.
8.Introduction to Turing Machines.
10. Intractable Problems.
11. Additional Classes of Problems.
Pearson offers special pricing when you package your text with other student resources. If you're interested in creating a cost-saving package for your students, contact your Pearson rep.
We're sorry! We don't recognize your username or password. Please try again.
Instructor resource file download
The work is protected by local and international copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning.
You have successfully signed out and will be required to sign back in should you need to download more resources.