Introduction to Automata Theory, Languages, and Computation

by Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D.

• ISBN13: 9780201441246
• ISBN10: 0201441241
• Edition: 2nd
• Format: Package
• Copyright: 2007-01-01
• Publisher: Addison Wesley

Summary

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.

Table of Contents

Automata: The Methods and the Madness

Why Study Automata Theory

Introduction to Formal Proof

Additional Forms of Proof

Inductive Proofs

The Central Concepts of Automata Theory

Summary of Chapter 1

Gradiance Problems for Chapter 1

References for Chapter 1

Finite Automata

An Informal Picture of Finite Automata

Deterministic Finite Automata

Nondeterministic Finite Automata

An Application_ Text Search

Finite Automata With EpsilonTransitions

Summary of Chapter 2

Gradiance Problems for Chapter 2

References for Chapter 2

Regular Expressions and Languages

Regular Expressions

Finite Automata and Regular Expressions

Applications of Regular Expressions

Algebraic Laws for Regular Expressions

Summary of Chapter 3

Gradiance Problems for Chapter 3

References for Chapter 3

Properties of Regular Languages

Proving Languages Not to Be Regular

Closure Properties of Regular Languages

Decision Properties of Regular Languages

Equivalence and Minimization of Automata

Summary of Chapter 4

Gradiance Problems for Chapter 4

References for Chapter 4

Context-Free Grammars and Languages

Context-Free Grammars

Parse Trees

Applications of Context-Free Grammars

Ambiguity in Grammars and Languages

Summary of Chapter 5

Gradiance Problems for Chapter 5

References for Chapter 5

Pushdown Automata

Definition of the Pushdown Automaton

The Languages of a PDA

Equivalence of PDA's and CFG's

Deterministic Pushdown Automata

Summary of Chapter 6

Gradiance Problems for Chapter 6

References for Chapter 6

Properties of Context-Free Languages

Normal Forms for Context-Free Grammars

The Pumping Lemma for Context-Free Languages

Closure Properties of Context-Free Languages

Decision Properties of CFL's

Summary of Chapter 7

Gradiance Problems for Chapter 7

References for Chapter 7

Introduction to Turing Machines

Problems That Computers Cannot Solve

The Turing Machine

Programming Techniques for Turing Machines

Extensions to the Basic Turing Machine

Restricted Turing Machines

Turing Machines and Computers

Summary of Chapter 8

Gradiance Problems for Chapter 8

References for Chapter 8

Undecidability

A Language That Is Not Recursively Enumerable

An Undecidable Problem That Is RE

Undecidable Problems About Turing Machines

Post's Correspondence Problem

Other Undecidable Problems

Summary of Chapter 9

Gradiance Problems for Chapter 9

References for Chapter 9

Intractable Problems

The Classes P and NP

An NP-Complete Problem

A Restricted Satisfiability Problem

Additional NP-Complete Problems

Summary of Chapter 10

Gradiance Problems for Chapter 10

References for Chapter 10

Additional Classes of Problems

Complements of Languages in NP

Problems Solvable in Polynomial Space

A Problem That Is Complete for PS

Language Classes Based on Randomization

The Complexity of Primality Testing

Summary of Chapter 11

Gradiance Problems for Chapter 11

References for Chapter 11

Index

Table of Contents provided by Publisher. All Rights Reserved.