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. |
Contents
The Methods and the Madness | 1 |
Reduction to Definitions | 8 |
Equivalence of Deterministic and Nondeterministic Finite | 55 |
Copyright | |
16 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
3SAT accepting algorithm alphabet automata blank boolean expression cells CFL's clause closure co-NP complement concatenation consider construction context-free grammar context-free languages counter machine defined deterministic DPDA e-NFA edges equivalent Example Exercises for Section Figure finite automaton G₁ Gradiance system grammar G graph halts Hamilton circuit homomorphism ID's inductive input symbol instance integer labeled leftmost derivation length M₁ moves MPCP multitape nodes nondeterministic Nondeterministic Finite Automata notation NP-complete O's and 1's O(n² Only-if operator P₁ pair parentheses parse tree path polynomial polynomial-time polynomial-time reduction proof prove pumping lemma pushdown pushdown automaton q₁ random recursive reduction regular expression regular languages replace represent sequence set of strings simulate solution statement steps suggested by Fig Suppose tape symbols Theorem TM's transition function truth assignment Turing machine undecidable variables