Models of Computation and Formal Languages presents a comprehensive and rigorous treatment of the theory of computability. The text takes a novel approach focusing on computational models and is the first book of its kind to feature companion software. Deus Ex Machina, developed by Nicolae Savoiu, comprises software simulations of the various computational models considered and incorporates numerous examples in a user-friendly format. Part I of the text introduces several universal models including Turing machines, Markov algorithms, and register machines. Complexity theory is integrated gradually, starting in Chapter 1. The vector machine model of parallel computation is covered thoroughly both in text and software. Part II develops the Chomsky hierarchy of formal languages and provides both a grammar-theoretic and an automata-theoretic characterization of each language family. Applications to programming languages round out an in-depth theoretical discussion, making this an ideal text for students approaching this subject for the first time. Ancillary sections of several chapters relate classical computability theory to the philosophy of mind, cognitive science, and theoretical linguistics. Ideal for Theory of Computability and Theory of Algorithms courses at the advanced undergraduate or beginning graduate level, Models of Computation and Formal Languages is one of the only texts that... · · Features accompanying software available on the World Wide Web at http://home.manhattan.edu/~gregory.taylor/thcomp/ Adopts an integrated approach to complexity theory · Offers a solutions manual containing full solutions to several hundred exercises. Most of these solutions are available to students on the World Wide Web at http://home.manhattan.edu/~gregory.taylor/thcomp · Features examples relating the theory of computation to the probable programming experience of an undergraduate computer science major

Preface 0. Mathematical Preliminaries .1. Sets and Set-Forming Operations .2. Introduction to Formal Language Theory .3. Mappings and Functions .4. Defining Functions Recursively .5. The Mathematics of Big-O Notation .6. Mathematical Induction .7. Graphs .8. Introduction to Propositional Logic .9. Two Important Proof Techniques .10. Defining Sets Recursively .11. Infinite Sets .12. Conjunctive Normal Form .13. Number-Theoretic Predicates .14. Further Reading Part I MODELS OF COMPUTATION 1 . Turing Machines 1.1. What Is Computation? 1.2. An Informal Description of Turing Machines 1.3. The Formal Definition of Turing Machines 1.4. Turing Machines as Language Acceptors and as Language Recognizers 1.5. Turing Machines as Computers of Number-Theoretic Functions 1.6. Modular Construction of Turing Machines 1.7. Introduction to Complexity Theory 1.8. Suggestions for Further Reading 2. Additional Varieties of Turing Machines 2.1. Turing Machines with One-Way-Infinite Tape 2.2. Turing Machines that Accept by Terminal Stare 2.3. Multitape Turing Machines 2.4. Encoding of Turing Machines 2.5. Universal Turing Machines 2.6. Nondeterministic Turing Machines 2.7. A Number-Theoretic FUnction That Is Not Turing-Computable 2.8. Turing Machines and Artificial Intelligence 2.9. Turing Machines and Cognitive Science 2.10. Regarding Theoretical Computer Science and Number-Theoretic Functions 2.11. Further Reading 3. An Introduction to Recursion Theory 3.1. The Primitive Recursive Functions 3.2. Primitive Recursive Predicates 3.3. The Partial Recursive Functions 3.4. The Class of Partial Recursive Functions Is Identical to the Class of Turing-Computable Functions 3.5. Recursive Sets 3.6. Recursively Enumerable Sets 3.7. Historical Remarks and Suggestions for Further Reading 4. Markov Algorithms 4.1. An Alternative Model of Sequential Computation 4.2. Markov Algorithms as Language Acceptors and as Language Recognizers 4.3. Markov Algorithms as Computers of Number-Theoretic Functions 4.4. Labeled Markov Algorithms 4.5. The Class of Markov-Computable Functions Is Identical to the Class of Partial Recursive Functions 4.6. Considerations of Efficiency 4.7. Computation Theory and the Foundations of Mathematics 4.8. Bibliography 5. Register Machines 5.1. Register Machines 5.2. The Class of Register-Machine-Computable Functions Is Identical to the Class of Partial Recursive Functions 5.3. Register Machines and Formal Languages 5.4. A Model-Independent Characterization of Computational Feasibility 5.5. Final Remarks and Suggestions for Further Reading 6. Post Systems (Optional) 6.1. Post Systems and Formal Languages 6.2. The Class of Post-Computable Functions Is Identical to the Class of Partial Recursive Functions 6.3. Closure Properties of the Class of Languages Generated by Post Systems 6.4. The Class of Languages Generated by Post Systems Is Identical to the Class of Turing-Acceptable Languages 6.5. Language Recognition and Post Systems 6.6. What Is a Model of Computation? 7. The Vector Machine Model of Parallel Computation (Optional) 7.1. What Is Parallel Computation? 7.2. Vectors and Vector Operations 7.3. Vector Machines 7.4. Vector Machines and Function Computation 7.5. Vector Machines and Formal Languages 7.6. Parallel Computation and Cognitive Science 7.7. Further Remarks 8. The Bounds of Computability 8.1. The Church-Turing Thesis 8.2. The Bounds of Computability-in-Principle: The Self-Halting Problem for Turing Machines 8.3. The Bounds of Computability-in-Principle: The Halting Problem for Turing Machines 8.4. The Bounds of Computability-in-Principle: Rice's Theorem 8.5. The Bounds of Feasible Computation: The Concept of NP-Completeness 8.6. An NP-Complete Problem (Cook-Levin Theorem) 8.7. Other NP-Complete Problems 8.8. The Bounds of Parallel Computation: The Concept of P-Completeness (Advanced) 8.9. A P-Complete Problem (Ladner's Theorem) (Advanced) 8.10. The Nearest-Neighbor Traveling Salesman Problem is P-Complete (Advanced) 8.11. Beyond Symbol Processing: The Connectionist Model of Cognition 8.12. Summary, Historical Remarks, and Suggestions for Further Reading 9. Part II FORMAL LANGUAGES AND AUTOMATARegular Languages and Finite-State Automata 9.1. Regular Expressions and Regular Languages 9.2. Deterministic Finite-State Automata 9.3. Nondeterministic Finite-State Automata 9.4. A Pumping Lemma for FSA-Acceptable Languages 9.5. Closure Properties of the Family of FSA-Acceptable Languages 9.6. The Family of Regular Languages Is Identical to the Family of FSA-Acceptable Languages 9.7. Finite-State Automata with Epsilon-Moves 9.8. Generative Grammars 9.9. Right-Linear Grammars and Regular Languages 9.10. Summary, Historical Remarks and Suggestions for Further Reading 10. Context-Free Languages and Pushdown-Stack Automata 10.1. Context-Free Grammars and Natural Languages 10.2. Normal Forms for Context-Free Grammars 10.3. Pushdown-Stack Automata 10.4. An Equivalent Notion of Word Acceptance for Pushdown-Stack Automata 10.5. The Class of Context-Free Languages Is Identical to the Class of PSA-Acceptable Languages 10.6. Closure Properties of the Family of Context-Free Languages 10.7. A Pumping Lemma for Context-Free Languages 10.8. Deterministic Context-Free Languages 10.9. Decidability Results for Context-Free Languages 10.10. Bibliography and Suggestions for Further Reading 11. Context-Sensitive Languages and Linear-Bounded Automata 11.1. Context-Sensitive Grammars 11.2. A Normal Form for Context-Sensitive Grammars 11.3. Linear-Bounded Automata 11.4. Context-Sensitive Languages and Linear-Bounded Automata 11.5. Closure Properties of the Family of Context-Sensitive Languages 11.6. The General Word Problem for Context-Sensitive Languages Is Solvable 11.7. There Exist Turing-Recognizable Languages That Are Not Context-Sensitive 11.8. Final Remarks 12. Generative Grammars and the Chomsky Hierarchy 12.1. Turing Machines and Phrase-Structure Languages 12.2. Closure Properties of the Family of Phrase-Structure Languages 12.3. Turing Machiens as Language Enumerators 12.4. A Recursion-Theoretic Characterization of the Family of Phrase-Structure Languages 12.5. The General Word Problem for Phrase-Structure Languages Is Unsolvable 12.6. The Post Correspondence Problem 12.7. The Chomsky Hierachy Epilogue Bibliography Index

R. Gregory TaylorChair, Department of Computer Science, New Jersey City University

"A comprehensive, advanced introductory textbook on the theory of computation that can be used on an undergraduate level as well as graduate. The solutions manual and software are welcome additions."--Philip Demp, Rutgers University