## Description

For upper level courses on Automata.

Combining classic theory with unique applications, this crisp narrative is supported by abundant examples and clarifies key concepts by introducing important uses of techniques in real systems. Broad-ranging coverage allows instructors to easily customize course material to fit their unique requirements.

Supplements Include:

- Solutions to most of the problems in the book as well as teaching tips, a complete set of lecture Power Point slides, additional exercises suitable for homework and exam questions.
- Companion Website

For more information please go to to www.prenhall.com/rich.

## Table of Contents

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 âSD 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

Appendices for Automata, Computability and Complexity: Theory and Applications:

- Math Background
- Working with Logical Formulas
- Finite State Machines and Regular Languages
- Context-Free Languages and PDAs
- Turing Machines and Undecidability
- Complexity
- Programming Languages and Compilers
- Tools for Programming, Databases and Software Engineering
- Networks
- Security
- Computational Biology
- Natural Language Processing
- Artificial Intelligence and Computational Reasoning
- Art & Entertainment: Music & Games
- Using Regular Expressions
- Using Finite State Machines and Transducers
- Using Grammars

## Purchase Info ?

With CourseSmart eTextbooks and eResources, you save up to 60% off the price of new print textbooks, and can switch between studying online or offline to suit your needs.

Once you have purchased your eTextbooks and added them to your CourseSmart bookshelf, you can access them anytime, anywhere.

Automata, Computability and Complexity: Theory and Applications, CourseSmart eTextbook

Format: Safari Book

$73.99 | ISBN-13: 978-0-13-513566-2