## Introduction to Automata Theory, Languages, and ComputationIt 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 |

### What people are saying - Write a review

#### LibraryThing Review

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

### Contents

The Methods and the Madness | 1 |

Finite Automata | 37 |

Regular Expressions and Languages | 83 |

Copyright | |

9 other sections not shown

### Other editions - View all

Introduction to Automata Theory, Languages, and Computation John E. Hopcroft,Rajeev Motwani,Jeffrey D. Ullman No preview available - 2003 |

### Common terms and phrases

3SAT accepting algorithm alphabet automaton binary blank boolean expression cells CFL's closure co-MV complement concatenation consider construction context-free grammar context-free languages counter machine defined deterministic DFA's DPDA e-NFA edges equivalent Example Exercises for Section Figure finite automata given graph halts Hamilton circuit homomorphism ID's inductive input symbol instance integer labeled leftmost derivation length moves MPCP multitape nodes nondeterministic Nondeterministic Finite Automata notation NP-complete number of O's O's and l's Only-if operator pair parentheses parse tree polynomial polynomial-time polynomial-time reduction proof prove pumping lemma pushdown automaton random recursive reduction regular expression regular languages replace represent sequence set of strings simulate solution stack symbols statement steps strings of O's suggested by Fig Suppose takes tape symbols terminal Theorem TM's transition function truth assignment Turing machine undecidable variables