Introduction to Automata Theory, Languages, and ComputationAddison-Wesley, 2001 - 521 стор. 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 |
Зміст
The Methods and the Madness | 1 |
Finite Automata | 37 |
Regular Expressions and Languages | 83 |
Авторські права | |
9 інших розділів не відображаються
Інші видання - Показати все
Introduction to Automata Theory, Languages, and Computation John E. Hopcroft,Rajeev Motwani,Jeffrey D. Ullman Попередній перегляд недоступний - 2003 |
Загальні терміни та фрази
3SAT accepting algorithm alphabet automaton binary blank boolean expression cells CFL's co-NP complement concatenation 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 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 number of 1's O's and 1's O(n² Only-if operator P₁ 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 0's suggested by Fig Suppose tape symbols terminal Theorem TM's transition function truth assignment Turing machine undecidable variables