AUTOMATA, COMPUTABILITY AND COMPLEXITY: THEORY AND APPLICATIONS (PIE)

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