Machines, Languages, and Computation

Theory of computation: Automata theory and formal languages, computability theory, and computational complexity theory, This is a textbook intended for undergrads at the senior level who are planning on graduate school. It explores the three underlying themes of theoretical computers mathematics, engineering, and linguistics. Each chapter includes problem sets, notes and references. The book includes an extensive bibliography and a detailed Subject Index. According to his web page bio Peter J Denning "was a pioneer in operating systems and computer networks and invented the working set, a way of automatically managing data flows in memory that is widely used in modern operating systems from desktops to smartphones... In the 1980s, while directing a research lab at NASA Ames Research Center, he became interested in how he could teach his students and researchers to be successful innovators, broadening his attentions to the human practices of technology adoption. Preface 1 Introduction 2 Logic, Set Theory, and Languages 3 Formal Grammars 4 Finite-State Machines 5 Finite-State Languages 6 Limitations of Finite Automata 7 Tape Automata 8 Pushdown Automata 9 Context-Free Languages 10 Syntax Analysis 11 Turing Machines 12 Unsolvable Problems 13 Recursive Functions 14 Post Systems Afterword Bibliography Index