Automata, Computability and Complexity: Theory and Applications (IE-Paperback)

<內容簡介>

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.

<章節目錄>

PART I: INTRODUCTION
1 Why Study Automata Theory of Mathematical Concepts?
2 Languages and Strings
3 The Big Picture: A Language Hierarchy
4 Computation
PART II: FINITE STATE MACHINES AND REGULAR LANGUAGES
5 Finite State Machines
6 Regular Expressions
7 Regular Grammars
8 Regular and Nonregular Languages
9 Algorithms and Decision Procedures for Regular Languages
10 Summary and References
PART III: CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA
11 Context-Free Grammars
12 Pushdown Automata
13 Context-Free and Noncontext-Free Languages
14 Algorithms and Decision Procedures for Context-Free Languages
15 Context-Free Parsing
16 Summary and References
PART IV: TURING MACHINES AND UNDECIDABILITY
17 Turing Machines
18 The Church-Turing Thesis
19 The Unsolvability of the Halting Problem
20 Decidable and Semidecidable Languages
21 Decidability and Undecidability Proofs
22 Decidable Languages That Do Not (Obviously) Ask Questions about Turing Machines
23 Unrestricted Grammars
24 The Chomsky Hierarchy and Beyond
25 Computable Functions
26 Summary and References
27 Introduction to the Analysis of Complexity
28 Time Complexity Classes
29 Space Complexity Classes
30 Practical Solutions for Hard Problems
31 Summary and References
References
Index