Skip to content

Automata, Computability and Complexity Theory and Applications

ISBN-10: 0132288060

ISBN-13: 9780132288064

Edition: 2008

Authors: Elaine A. Rich

List price: $206.60
Shipping box This item qualifies for FREE shipping.
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!


Combining classic theory with unique applications and examples, this reader-friendly guide offers a practical, broad-based introduction to automata theory.Application-oriented approach demonstrates why the study of theory will make readers better system designers and builders. 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. Includes discussion of unique applications such as computational biology. Uses consistent, easily understandable formats to indicate definitions and name variables and objects. For those interested in learning more about automata theory.
Customers also bought

Book details

List price: $206.60
Copyright year: 2008
Publisher: Prentice Hall PTR
Publication date: 9/18/2007
Binding: Hardcover
Pages: 1120
Size: 7.25" wide x 9.50" long x 1.75" tall
Weight: 4.048

Why Study Automata Theory?
Review of Mathematical Concepts
Proof Techniques
Reasoning about Programs
Languages and Strings
The Big Picture: A Language Hierarchy
Defining the Task: Language Recognition
The Power of Encoding
A Hierarchy of Language Classes5 Computation
Decision Procedures
Determinism and Nondeterminism
Functions on Languages and Programs
Finite State Machines and Regular Languages
Finite State Machines
Deterministic Finite State Machines
The Regular Languages
Programming Deterministic Finite State Machines
Nondeterministic FSMs
Interpreters for FSMs
Minimizing FSMs
Finite State Transducers
Bidirectional Transducers
Stochastic Finite Automata
Finite Automata, Infinite Strings: Buchi Automata
Regular Expressions
What is a Regular Expression?
Kleene's Theorem
Applications of Regular Expressions
Manipulating and Simplifying Regular Expressions
Regular Grammars
Definition of a Regular Grammar
Regular Grammars and Regular Languages
Regular and Nonregular Languages
How Many Regular Languages Are There?
Showing That a Language Is Regular.124
Some Important Closure Properties of Regular Languages
Showing That a Language is Not Regular
Exploiting Problem-Specific Knowledge
Functions on Regular Languages
Algorithms and Decision Procedures for Regular Languages
Fundamental Decision Procedures
Summary of Algorithms and Decision Procedures for Regular Languages
Summary and References
Context-Free Languages and Pushdown Automata 144
Context-Free Grammars
Introduction to Grammars
Context-Free Grammars and Languages
Designing Context-Free Grammars
Simplifying Context-Free Grammars
Proving That a Grammar is Correct
Derivations and Parse Trees
Normal Forms
Stochastic Context-Free Grammars
Pushdown Automata
Definition of a (Nondeterministic) PDA
Deterministic and Nondeterministic PDAs
Equivalence of Context-Free Grammars and PDAs
Nondeterminism and Halting
Alternative Definitions of a PDA
Context-Free and Noncontext-Free Languages
Where Do the Context-Free Languages Fit in the Big Picture?
Showing That a Language is Context-Free
The Pumping Theorem for Context-Free Languages
Some Important Closure Properties of Context-Free Languages
Deterministic Context-Free Languages
Other Techniques for Proving That a Language is Not Context-Free
Algorithms and Decision Procedures for Context-Free Languages
Fundamental Decision Procedures
Summary of Algorithms and Decision Procedures for Context-Free Languages
Context-Free Parsing
Lexical Analysis
Top-Down Parsing
Bottom-Up Parsing
Parsing Natural Languages
Stochastic Parsing
Summary and References
Turing Machines and Undecidability
Turing Machines
Definition, Notation and Examples
Computing With Turing Machines
Turing Machines: Extensions and Alternativ