Description

Features

• Focus on applications – Demonstrates why studying theory will make them better system designers and builders.

• Classic theory combined with new applications – Includes fresh discussion of applications such as computational biology.

• Review of background mathematical concepts (Ch. 2) – Addresses students’ varying backgrounds in discrete mathematics and logic.

• Clear notation and naming conventions – Uses consistent, easily understandable formats to indicate definitions and name variables and objects.

• Thorough coverage of automata theory:

–       Features topics such as use of the closure theorems for regular and context-free languages, ambiguity in context-free grammars, parsing, functions on languages, and decision procedures for regular and context-free languages.

–       Also includes coverage of top-down and bottom-up parsers, stochastic automata, context-sensitive languages, the Chomsky hierarchy, and recursive functions.

• Comprehensive appendices referenced throughout the text as boxed features – Appendix A treats selected theoretical concepts in greater depth; Appendix B describes applications of the techniques that are described in the main body of the book, and Appendix C augments the core material with historical, biographical and entertaining notes. 

• Optional material for longer courses – Clearly indicates additional material that may be introduced at the instructor’s discretion without loss of continuity. Optional topics include: FSM minimization, stochastic FSMs (HMMs), Büchi automata, deterministic context-free languages, Ogden’s Lemma, Parikh’s Theorem, and others.

• Companion website – Organized to follow the organization of the text, the companion website provides a host of additional materials and activities, plus updates on the evolving uses of theory in various application areas.

• Hundreds of problems and solutions – Suitable for in-class practice, homework, or exams.

• Instructor support – Includes complete PowerPoint® slides to simplify lecture preparation.

Table of Contents

CO>

PART I: INTRODUCTION

1 Why Study Automata Theory?

2 Review of Mathematical Concepts

2.1 Logic

2.2 Sets

2.3 Relations

2.4 Functions

2.5 Closures

2.6 Proof Techniques

2.7 Reasoning about Programs

2.8 References

3 Languages and Strings

3.1 Strings

3.2 Languages

4 The Big Picture: A Language Hierarchy

4.1 Defining the Task: Language Recognition

4.2 The Power of Encoding

4.3 A Hierarchy of Language Classes

5 Computation

5.1 Decision Procedures

5.2 Determinism and Nondeterminism

5.3 Functions on Languages and Programs

PART II: FINITE STATE MACHINES AND REGULAR LANGUAGES

6 Finite State Machines

6.2 Deterministic Finite State Machines

6.3 The Regular Languages

6.4 Programming Deterministic Finite State Machines

6.5 Nondeterministic FSMs

6.6 Interpreters for FSMs

6.7 Minimizing FSMs

6.8 Finite State Transducers

6.9 Bidirectional Transducers

6.10 Stochastic Finite Automata

6.11 Finite Automata, Infinite Strings: Büchi Automata

6.12 Exercises

7 Regular Expressions

7.1 What is a Regular Expression?

7.2 Kleene’s Theorem

7.3 Applications of Regular Expressions

7.4 Manipulating and Simplifying Regular Expressions

8 Regular Grammars

8.1 Definition of a Regular Grammar

8.2 Regular Grammars and Regular Languages

8.3 Exercises

9 Regular and Nonregular Languages

9.1 How Many Regular Languages Are There?

9.2 Showing That a Language Is Regular.124

9.3 Some Important Closure Properties of Regular Languages

9.4 Showing That a Language is Not Regular

9.5 Exploiting Problem-Specific Knowledge

9.6 Functions on Regular Languages

9.7 Exercises

10 Algorithms and Decision Procedures for Regular Languages

10.1 Fundamental Decision Procedures

10.2 Summary of Algorithms and Decision Procedures for Regular Languages

10.3 Exercises

11 Summary and References

PART III: CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA 144

12 Context-Free Grammars

12.1 Introduction to Grammars

12.2 Context-Free Grammars and Languages

12.3 Designing Context-Free Grammars

12.4 Simplifying Context-Free Grammars

12.5 Proving That a Grammar is Correct

12.6 Derivations and Parse Trees

12.7 Ambiguity

12.8 Normal Forms

12.9 Stochastic Context-Free Grammars

12.10 Exercises

13 Pushdown Automata

13.1 Definition of a (Nondeterministic) PDA

13.2 Deterministic and Nondeterministic PDAs

13.3 Equivalence of Context-Free Grammars and PDAs

13.4 Nondeterminism and Halting

13.5 Alternative Definitions of a PDA

13.6 Exercises

14 Context-Free and Noncontext-Free Languages

14.1 Where Do the Context-Free Languages Fit in the Big Picture?

14.2 Showing That a Language is Context-Free

14.3 The Pumping Theorem for Context-Free Languages

14.4 Some Important Closure Properties of Context-Free Languages

14.5 Deterministic Context-Free Languages

14.6 Other Techniques for Proving That a Language is Not Context-Free

14.7 Exercises

15 Algorithms and Decision Procedures for Context-Free Languages

15.1 Fundamental Decision Procedures

15.2 Summary of Algorithms and Decision Procedures for Context-Free Languages

16 Context-Free Parsing

16.1 Lexical Analysis

16.2 Top-Down Parsing

16.3 Bottom-Up Parsing

16.4 Parsing Natural Languages

16.5 Stochastic Parsing

16.6 Exercises

17 Summary and References

PART IV: TURING MACHINES AND UNDECIDABILITY

18 Turing Machines

18.1 Definition, Notation and Examples

18.2 Computing With Turing Machines

18.3 Turing Machines: Extensions and Alternative Definitions

18.4 Encoding Turing Machines as Strings

18.5 The Universal Turing Machine

18.6 Exercises

19 The Church-Turing

19.1 The Thesis

19.2 Examples of Equivalent Formalisms

20 The Unsolvability of the Halting Problem

20.1 The Language H is Semidecidable but Not Decidable

20.2 Some Implications of the Undecidability of H

20.3 Back to Turing, Church, and the Entscheidungsproblem

21 Decidable and Semidecidable Languages

21.2 Subset Relationships between D and SD

21.3 The Classes D and SD Under Complement

21.4 Enumerating a Language

21.5 Summary

21.6 Exercises

22 Decidability and Undecidability Proofs

22.1 Reduction

22.2 Using Reduction to Show that a Language is Not Decidable

22.3 Rice’s Theorem

22.4 Undecidable Questions About Real Programs

22.5 Showing That a Language is Not Semidecidable

22.6 Summary of D, SD/D and ¿ Languages that Include Turing Machine Descriptions

22.7 Exercises

23 Undecidable Languages That Do Not Ask Questions about Turing Machines

23.1 Hilbert’s 10th Problem

23.2 Post Correspondence Problem

23.3 Tiling Problems

23.4 Logical Theories

23.5 Undecidable Problems about Context-Free Languages

APPENDIX C: HISTORY, PUZZLES, AND POEMS

43 Part I: Introduction

43.1 The 15-Puzzle

Part II: Finite State Machines and Regular Languages

44.1 Finite State Machines Predate Computers

44.2 The Pumping Theorem Inspires Poets

REFERENCES

INDEX

Courses

Automata / Theory of Computation  (Computer Science)

Author Bios

Elaine Rich received her Ph.D. in Computer Science from Carnegie-Mellon in 1979.  Her thesis, Building and Exploiting User Models, laid the groundwork for the next twenty years of work on personalizing information systems to meet the needs of individual users.  Over twenty years later, she still gets requests for her thesis and the papers based on it.

Dr. Rich joined the UT CS faculty in 1979.  She continued her work in the area of human/machine interfaces, with a focus on the use of knowledge-based systems.  She was PI on an NSF grant, "Individual Models in Computer Systems", $56,000, NSF, 1980, which supported that work.  She was also co-PI on two other grants while at UT: "An Experimental Computing Facility to Support the Design and Analysis of Reliable, High Performance Computing Systems", with J. C. Browne, A. G. Dale, D. I. Good, and A. Silberschatz, $3,700,000, NSF, 1982 and "Support for an AI Laboratory", with G. Novak, R. Simmons, and V. Kumar, $1,300,000, Army Research Office, 1984.  The $3.7M NSF grant is particularly significant.  It supported, for the first time in our department's history, a significant investment in the computing and networking infrastructure required to enable research groups to cooperate in work that required building large software systems.

In 1985, Dr. Rich left UT for the Microelectronic and Computing Technology Corporation (MCC).  She served first as a Member of the Technical Staff, then Associate Director of the Human Interface Lab, then Director of the Artificial Intelligence Lab.  At MCC, she was responsible for attracting and maintaining support, from MCC's corporate shareholders, for the research projects in her lab.  Dr. Rich was responsible for setting research agendas, for enabling technology transfer from MCC to the shareholder companies, and for managing the lab's annual budgets (between $1M and $3M per year).

In 1998, Dr. Rich returned to the CS department at UT Austin as a Senior Lecturer.  She has taught Automata Theory, Artificial Intelligence, and Natural Language Processing.  She served for two years as Associate Chair for Academic Affairs in the department.  During that time, she oversaw a major redesign of the undergraduate curriculum, as well as the launch of several new programs including Turing Scholars, an undergraduate honors program and First Bytes, a summer camp for high school girls to encourage their interest in computer science.

In 1983, Dr. Rich published her textbook, Artificial Intelligence, from which at least a decade of the world's computer scientists learned AI.  The book was translated into Japanese, French, Spanish, German, Italian and Portugese.  In 1991, with Kevin Knight, she published a second edition.  The two editions have sold over 250,000 copies.

Dr. Rich has published nine book chapters and 24 refereed papers.   She has served as Editor of AI Magazine and on the editorial boards of Artificial Intelligence Review, The Knowledge Engineering Review, User Modeling and User-Adapted Interaction, and Applied Intelligence.  She has served on numerous review panels for NSF and on the Discipline Advisory Committee of the Council of International Exchange of Scholars.  In 1991, she was elected a Fellow of the American Association for Artificial Intelligence.

Companion Website for Automata, Computability and Complexity: Theory and Applications
Rich
©2008  |  Prentice Hall  |  Website  |  Live
ISBN-10: 0136027601  |  ISBN-13: 9780136027607
This online resource is available at no cost at http://www.prenhall.com/rich.
More Info

Downloadable Instructor Resources

Show All Downloadable Files

Hide All Downloadable Files

|

Help Downloading Files

Instructor Resource Center for Automata, Computability and Complexity: Theory and Applications
Rich
©2008  |  Prentice Hall  |  On-line Supplement  |  Live
ISBN-10: 0136056008  |  ISBN-13: 9780136056003

Show Downloadable Files

Hide Downloadable Files

|

More Info

Back to top

Companion Website for Automata, Computability and Complexity: Theory and Applications
Rich
©2008  |  Prentice Hall  |  Website  |  Live
ISBN-10: 0136027601  |  ISBN-13: 9780136027607
This online resource is available at no cost at http://www.prenhall.com/rich.
More Info

Back to top

Companion Website for Automata, Computability and Complexity: Theory and Applications
Rich
©2008  |  Prentice Hall  |  Website  |  Live
ISBN-10: 0136027601  |  ISBN-13: 9780136027607
This online resource is available at no cost at http://www.prenhall.com/rich.
More Info

Companion Website for Automata, Computability and Complexity: Theory and Applications
Rich
©2008  |  Prentice Hall  |  Website  |  Live
ISBN-10: 0136027601  |  ISBN-13: 9780136027607
This online resource is available at no cost at http://www.prenhall.com/rich.
More Info

Back to top

Give your students a choice! PearsonChoices products are designed to give your students more value and flexibility by letting them choose from a variety of text and media formats to best match their learning style and their budget.

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students, see the Packages Tab.

• Automata, Computability and Complexity: Theory and Applications, CourseSmart eTextbook
  Rich
  ©2008  |  Prentice Hall  |  Electronic Book; 1120 pp  |  Available
  ISBN-10: 0135135664  |  ISBN-13: 9780135135662
  Online purchase price: $59.99Brief Description  | 

  

  CourseSmart eTextbooks are a creative digital solution that offers the freedom and convenience of online, offline, and mobile access using a single platform. With a CourseSmart eTextbook, students can:

  • search the text

  • make notes online

  • print out reading assignments that incorporate lecture notes

  • bookmark important passages for later review

  • save money. As an alternative to purchasing the print textbook, students can subscribe to the same content online for a significant discount off the suggested list price of the print text.

  For more information, or to subscribe to the CourseSmart eTextbook, visit www.coursesmart.com (for customers in U.S. and Canada) or www.coursesmart.co.uk (for customers in Europe, Middle East, and Africa).

  More Info  |  Students, buy access
  

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students contact your Pearson Higher Education representative.