Introduction to computer theory /
Daniel I.A. Cohen.
- 2nd ed.
- New York : Wiley, 1991.
- xii, 838 p. : 25 cm.
PART I AUTOMATA THEORY 1 Background 2 Languages Languages in the Abstract 7 Introduction to Defining Languages 10 Kieene Closure 14 Problems 19 3 Recursive Definitions A New Method for Defining Languages 21 An Important Language: Arithemetic Expressions 25 Problems 28 4 Regular Expressions Defining Languages by Another New Method 31 Formal Definition of Regular Expressions 35 Languages Associated with Regular Expressions 43 Finite Languages Are Regular 44 How Hard It Is To Understand a Regular Expression 45 Introducing EVEN-EVEN 48 Problems 49 5 Finite Automata Yet Another Method for Defining Languages 52 FAs and Their Languages 59 EVEN-EVEN Revisited 69 Problems 71 6 IVansition Graphs Relaxing the Restriction on Inputs 76 Looking at TGs 81 Generalized Transition Graphs 86 Nondeterminism 87 Problems 88 7 Kleene's Theorem Unification 92 Tuming TGs into Regular Expressions 93 Converting Regular Expressions into FAs 108 Nondeterministic Finite Automata 135 NFAs and Kleene's Theorem 140 Problems 142 8 Finite Automata with Output Moore Machines 149 Mealy Machines 152 Moore = Mealy 156 Transducers as Models of Sequential Circuits 161 Problems 164 9 Regular Languages Closure Properties 169 Complements and Intersections 172 Problems 185 10 Nonregular Languages The Pumping Lemma 187 The Myhill - Nerode Theorem 196 Quotient Languages 200 Problems 203 11 Decidability Equivalence 207 Finiteness 214 Problems 217 PART II PUSHDOWN AUTOMATA THEORY 12 Context-Free Grammars Syntax as a Method for Defining Languages 224 Symbolism for Generative Grammars 230 Trees 241 Lukasiewicz Notation 245 Ambiguity 250 The Total Language Tree 252 Problems 254 13 Grammatical Format Regular Grammars 259 Killing A-Productions 265 Killing Unit Productions 272 Chomsky Normal Form 275 Leftmost Derivations 282 Problems 285 14 Pushdown Automata A New Fcirnat for FAs 289 Adding a Pushdown Stack 293 Defining the PDA 307 Problems 312 15 CFG = PDA Building a PDA for Every CFG 318 Building a CFG for Every PDA 327 Problems 348 16 Non-Context-Free Languages Self-Embeddedness 351 The Pumping Lemma for CFLs 360 Problems 373 17 Context-Free Languages Closure Properties 376 Intersection and Complement 385 Mixing Context-Free and Regular Languages 393 Problems 398 18 Decidability Emptiness and Uselessness 402 Finiteness 408 Membership—The CYK Algorithm 410 Parsing Simple Arithmetic 415 Problems 429 19 Ttiring Machines PART III TURING THEORY The Turing Machine 434 The Subprogram INSERT 449 The Subprogram DELETE 452 Problems 454 20 Post Machines The Post Machine 457 Simulating a PM on a TM 462 Simulating a TM on a PM 468 Problems 477 21 Minsky's Theorem The Two-Stack PDA 480 Just Another TM 482 Problems 492 22 Variations on the TM The Move-in-State Machine 494 The Stay-Option Machine 499 The^-TrackTM 502 The Two-Way Infinite Tape Model 511 The Nondeterministic TM 518 The Read-only TM 524 Problems 531 23 TM Languages Recursively Enumerable Languages 535 The Encoding of Turing Machines 545 A Non-Recursively Enumerable Language 549 The Universal Turing Machine 552 Not All r.e. Languages Are Recursive 557 Decidability 558 Problems 562 24 The Chomsky Hierarchy Phrase-Structure Grammars 565 TypeO = TM 574 The Product and Kleene Closure of r.e. Languages 586 Context-Sensitive Grammars 588 Problems 590 25 Computers Defining the Computer 594 Computable Functions 599 Church's Thesis 610 TMs as Language Generators 612 Problems 616