Languages and Machines
Subtitle: An Introduction to the Theory of Computer Science (2nd Edition)
Publisher: Addison Wesley; Addison-Wesley Pub.
Published: November 4, 1996
Language: eng
Number of pages: 569
ISBN-13: 9780201821369
Table of contents: title: Introduction
pagenum: 1; label: Part I
title: Foundations; label: Chapter 1
title: Mathematical Preliminaries
pagenum: 7; label: 1.1
title: Set Theory
pagenum: 8; label: 1.2
title: Cartesian Product, Relations, and Functions
pagenum: 11; label: 1.3
title: Equivalence Relations
pagenum: 13; label: 1.4
title: Countable and Uncountable Sets
pagenum: 15; label: 1.5
title: Recursive Definitions
pagenum: 20; label: 1.6
title: Mathematical Induction
pagenum: 24; label: 1.7
title: Directed Graphs
pagenum: 28; title: Exercises
pagenum: 33; title: Bibliographic Notes
pagenum: 36; label: Chapter 2
title: Languages
pagenum: 37; label: 2.1
title: Strings and Languages
pagenum: 37; label: 2.2
title: Finite Specification of Languages
pagenum: 41; label: 2.3
title: Regular Sets and Expressions
pagenum: 44; title: Exercises
pagenum: 49; title: Bibliographic Notes
pagenum: 51; label: Part II
title: Context-Free Grammars and Parsing; label: Chapter 3
title: Context-Free Grammars
pagenum: 55; label: 3.1
title: Context-Free Grammars and Languages
pagenum: 58; label: 3.2
title: Examples of Grammars and Languages
pagenum: 66; label: 3.3
title: Regular Grammars
pagenum: 71; label: 3.4
title: Grammars and Languages Revisited
pagenum: 72; label: 3.5
title: A Context-Free Grammar for Pascal
pagenum: 78; label: 3.6
title: Arithmetic Expressions
pagenum: 79; title: Exercises
pagenum: 82; title: Bibliographic Notes
pagenum: 85; label: Chapter 4
title: Parsing: An Introduction
pagenum: 87; label: 4.1
title: Leftmost Derivations and Ambiguity
pagenum: 88; label: 4.2
title: The Graph of a Grammar
pagenum: 92; label: 4.3
title: A Breadth-First Top-Down Parser
pagenum: 93; label: 4.4
title: A Depth-First Top-Down Parser
pagenum: 99; label: 4.5
title: Bottom-Up Parsing
pagenum: 104; label: 4.6
title: A Depth-First Bottom-Up Parser
pagenum: 107; title: Exercises
pagenum: 111; title: Bibliographic Notes
pagenum: 115; label: Chapter 5
title: Normal Forms
pagenum: 117; label: 5.1
title: Elimination of Lambda Rules
pagenum: 117; label: 5.2
title: Elimination of Chain Rules
pagenum: 125; label: 5.3
title: Useless Symbols
pagenum: 129; label: 5.4
title: Chomsky Normal Form
pagenum: 134; label: 5.5
title: Removal of Direct Left Recursion
pagenum: 137; label: 5.6
title: Greibach Normal Form
pagenum: 140; title: Exercises
pagenum: 147; title: Bibliographic Notes
pagenum: 152; label: Part III
title: Automata and Languages; label: Chapter 6
title: Finite Automata
pagenum: 155; label: 6.1
title: A Finite-State Machine
pagenum: 156; label: 6.2
title: Deterministic Finite Automata
pagenum: 157; label: 6.3
title: State Diagrams and Examples
pagenum: 162; label: 6.4
title: Nondeterministic Finite Automata
pagenum: 168; label: 6.5
title: Lambda Transitions
pagenum: 172; label: 6.6
title: Removing Nondeterminism
pagenum: 175; label: 6.7
title: DFA Minimization
pagenum: 182; title: Exercises
pagenum: 188; title: Bibliographic Notes
pagenum: 195; label: Chapter 7
title: Regular Languages and Sets
pagenum: 197; label: 7.1
title: Finite Automata and Regular Sets
pagenum: 197; label: 7.2
title: Expression Graphs
pagenum: 200; label: 7.3
title: Regular Grammars and Finite Automata
pagenum: 204; label: 7.4
title: Closure Properties of Regular Languages
pagenum: 208; label: 7.5
title: A Nonregular Language
pagenum: 209; label: 7.6
title: The Pumping Lemma for Regular Languages
pagenum: 212; label: 7.7
title: The Myhill-Nerode Theorem
pagenum: 217; title: Exercises
pagenum: 223; title: Bibliographic Notes
pagenum: 226; label: Chapter 8
title: Pushdown Automata and Context-Free Languages
pagenum: 227; label: 8.1
title: Pushdown Automata
pagenum: 227; label: 8.2
title: Variations on the PDA Theme
pagenum: 233; label: 8.3
title: Pushdown Automata and Context-Free Languages
pagenum: 236; label: 8.4
title: The Pumping Lemma for Context-Free Languages
pagenum: 242; label: 8.5
title: Closure Properties of Context-Free Languages
pagenum: 246; label: 8.6
title: A Two-Stack Automaton
pagenum: 250; title: Exercises
pagenum: 252; title: Bibliographic Notes
pagenum: 257; label: Chapter 9
title: Turing Machines
pagenum: 259; label: 9.1
title: The Standard Turing Machine
pagenum: 259; label: 9.2
title: Turing Machines as Language Acceptors
pagenum: 263; label: 9.3
title: Alternative Acceptance Criteria
pagenum: 265; label: 9.4
title: Multitrack Machines
pagenum: 267; label: 9.5
title: Two-Way Tape Machines
pagenum: 269; label: 9.6
title: Multitape Machines
pagenum: 272; label: 9.7
title: Nondeterministic Turing Machines
pagenum: 278; label: 9.8
title: Turing Machines as Language Enumerators
pagenum: 284; title: Exercises
pagenum: 291; title: Bibliographic Notes
pagenum: 295; label: Chapter 10
title: The Chomsky Hierarchy
pagenum: 297; label: 10.1
title: Unrestricted Grammars
pagenum: 297; label: 10.2
title: Context-Sensitive Grammars
pagenum: 304; label: 10.3
title: Linear-Bounded Automata
pagenum: 306; label: 10.4
title: The Chomsky Hierarchy
pagenum: 309; title: Exercises
pagenum: 310; title: Bibliographic Notes
pagenum: 313; label: Part IV
title: Decidability and Computability; label: Chapter 11
title: Decidability
pagenum: 317; label: 11.1
title: Decision Problems
pagenum: 318; label: 11.2
title: The Church-Turing Thesis
pagenum: 321; label: 11.3
title: The Halting Problem for Turing Machines
pagenum: 323; label: 11.4
title: A Universal Machine
pagenum: 327; label: 11.5
title: Reducibility
pagenum: 328; label: 11.6
title: Rice's Theorem
pagenum: 332; label: 11.7
title: An Unsolvable Word Problem
pagenum: 335; label: 11.8
title: The Post Correspondence Problem
pagenum: 337; label: 11.9
title: Undecidable Problems in Context-Free Grammars
pagenum: 343; title: Exercises
pagenum: 346; title: Bibliographic Notes
pagenum: 349; label: Chapter 12
title: Numeric Computation
pagenum: 351; label: 12.1
title: Computation of Functions
pagenum: 351; label: 12.2
title: Numeric Computation
pagenum: 354; label: 12.3
title: Sequential Operation of Turing Machines
pagenum: 357; label: 12.4
title: Composition of Functions
pagenum: 364; label: 12.5
title: Uncomputable Functions
pagenum: 368; label: 12.6
title: Toward a Programming Language
pagenum: 369; title: Exercises
pagenum: 376; title: Bibliographic Notes
pagenum: 379; label: Chapter 13
title: Mu-Recursive Functions
pagenum: 381; label: 13.1
title: Primitive Recursive Functions
pagenum: 382; label: 13.2
title: Some Primitive Recursive Functions
pagenum: 386; label: 13.3
title: Bounded Operators
pagenum: 390; label: 13.4
title: Division Functions
pagenum: 395; label: 13.5
title: Gödel Numbering and Course-of-Values Recursion
pagenum: 397; label: 13.6
title: Computable Partial Functions
pagenum: 401; label: 13.7
title: Turing Computability and Mu-Recursive Functions
pagenum: 406; label: 13.8
title: The Church-Turing Thesis Revisited
pagenum: 412; title: Exercises
pagenum: 415; title: Bibliographic Notes
pagenum: 421; label: Part V
title: Computational Complexity; label: Chapter 14
title: Computational Complexity
pagenum: 425; label: 14.1
title: Time Complexity of a Turing Machine
pagenum: 425; label: 14.2
title: Linear Speedup
pagenum: 429; label: 14.3
title: Rates of Growth
pagenum: 433; label: 14.4
title: Complexity and Turing Machine Variations
pagenum: 437; label: 14.5
title: Properties of Time Complexity
pagenum: 439; label: 14.6
title: Nondeterministic Complexity
pagenum: 446; label: 14.7
title: Space Complexity
pagenum: 447; title: Exercises
pagenum: 450; title: Bibliographic Notes
pagenum: 452; label: Chapter 15
title: Tractability and NP-Complete Problems
pagenum: 453; label: 15.1
title: Tractable and Intractable Decision Problems
pagenum: 454; label: 15.2
title: The Class NP
pagenum: 457; label: 15.3
title: P = NP?
pagenum: 458; label: 15.4
title: The Satisfiability Problem
pagenum: 461; label: 15.5
title: Additional NP-Complete Problems
pagenum: 472; label: 15.6
title: Derivative Complexity Classes
pagenum: 482; title: Exercises
pagenum: 485; title: Bibliographic Notes
pagenum: 486; label: Part VI
title: Deterministic Parsing; label: Chapter 16
title: LL(k) Grammars
pagenum: 489; label: 16.1
title: Lookahead in Context-Free Grammars
pagenum: 489; label: 16.2
title: FIRST, FOLLOW, and Lookahead Sets
pagenum: 494; label: 16.3
title: Strong LL(k) Grammars
pagenum: 496; label: 16.4
title: Construction of FIRST Sets
pagenum: 498; label: 16.5
title: Construction of FOLLOWk Sets
pagenum: 501; label: 16.6
title: A Strong LL(1) Grammar
pagenum: 503; label: 16.7
title: A Strong LL(k) Parser
pagenum: 505; label: 16.8
title: LL(k) Grammars
pagenum: 507; title: Exercises
pagenum: 509; title: Bibliographic Notes
pagenum: 511; label: Chapter 17
title: LR(k) Grammars
pagenum: 513; label: 17.1
title: LR(0) Contexts
pagenum: 513; label: 17.2
title: An LR(0) Parser
pagenum: 517; label: 17.3
title: The LR(0) Machine
pagenum: 519; label: 17.4
title: Acceptance by the LR(0) Machine
pagenum: 524; label: 17.5
title: LR(1) Grammars
pagenum: 530; title: Exercises
pagenum: 538; title: Bibliographic Notes
pagenum: 540; label: Appendix I
title: Index of Notation
pagenum: 541; label: Appendix II
title: The Greek Alphabet
pagenum: 545; label: Appendix III
title: Backus-Naur Definition of Pascal
pagenum: 547; title: Bibliography
pagenum: 553; title: Subject Index
pagenum: 561