## Introduction to Automata Theory, Languages, and ComputationThis classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with the increase of hands-on, practical applications. This new edition comes with Gradiance, an online assessment tool developed for computer science. Gradiance is the most advanced online assessment tool developed for the computer science discipline. With its innovative underlying technology, Gradiance turns basic homework assignments and programming labs into an interactive learning experience for students. By using a series of root questions and hints, it not only tests a student's capability, but actually simulates a one-on-one teacher-student tutorial that allows for the student to more easily learn the material. Through the programming labs, instructors are capable of testing, tracking, and honing their students' skills, both in terms of syntax and semantics, with an unprecedented level of assessment never before offered. For more information about Gradiance, please visit www.aw.com/gradiance. |

### 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 | 85 |

Copyright | |

11 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 - 2007 |

### Common terms and phrases

0's and l's 3SAT accepting algorithm alphabet boolean expression CFL's closure complement concatenation consider consisting construction context-free grammar context-free languages convert defined describe deterministic DFA's distinguishable e-NFA edges eliminate equivalent example Exercises for Section Figure finite automata given Gradiance system grammar G graph homomorphism ID's inductive input symbol instance integer labeled leftmost derivation length lexical analyzer moves MPCP multitape nodes nondeterministic nondeterministic finite automata notation NP-complete number of 0's Only-if operator pair palindromes parentheses parse tree path polynomial polynomial-time polynomial-time reduction productions proof prove pumping lemma pushdown automaton random reachable recursive reduction regular expression regular languages replace represent rule sequence set of strings simulate solution statement step strings of 0's Suppose tape symbols terminal Theorem transition function truth assignment Turing machine undecidable union variables