The Language of Machines: An Introduction to Computability and Formal Languages

Description

An up-to-date, authoritative text for courses in theory of computability and languages. The authors redefine the building blocks of automata theory by offering a single unified model encompassing all traditional types of computing machines and "real world" electronic computers. This reformulation of computablity and formal language theory provides a framework for building a body of knowledge. A solutions manual and an instructor's software disk are also available. ** The Language of Machines: An Introduction to Computability and Formal Languages......Page 2 Library of Congress Cataloging-in -Publication Data......Page 4 CONTENTS......Page 5 PREFACE......Page 10 ACKNOWLEDGMENTS......Page 14 ABOUT THE AUTHORS......Page 16 0 Mathematical Preliminaries......Page 17 0.1 QUANTIFIERS AND TWO - PLAYER GAMES......Page 18 0.2 SETS , BAGS, RELATIONS , FUNCTIONS, AND SEQUENCES......Page 21 0.2.1 Sets......Page 22 0.2.2 Set Extensions and Closures......Page 25 0.2.3 Tuples......Page 29 0.2.4 Sequences......Page 31 0.2.5 Bags......Page 32 0.2.6 Relations......Page 34 0.2.7 Functions......Page 40 Exercises......Page 43 0.3 STRINGS......Page 45 0.3.1 Regular Operations......Page 47 0.3.2 Miscellaneous String Operations and Relations......Page 48 0.3.3 b-ary and b-adic Number Representations......Page 49 Exercises......Page 51 0.4 GRAPHS......Page 52 0.5 BIG-O NOTATION......Page 54 0.6 INDUCTION......Page 55 Exercises......Page 63 0.6.1 Strong Induction......Page 67 Exercises......Page 70 0.6.2 Pigeonhole Principle......Page 71 Exercises......Page 73 0.6.3 Recursive Definitions......Page 76 Exercises......Page 80 1 Introduction to Machines......Page 83 1.1 PROGRAMS......Page 84 Exercises......Page 94 1.2 CONTROLS......Page 96 Exercises......Page 97 1.3 UNSIGNED COUNTERS......Page 98 Exercises......Page 101 1.4 SIGNED COUNTERS......Page 102 1.5 STACKS......Page 103 Exercises......Page 105 1.7 TURING MACHINES......Page 107 1.8 RANDOM ACCESS MACHINES......Page 112 1.9 DETERMINISM AND NONDETERMINISM......Page 115 Exercises......Page 122 1.10 CHAPTER SUMMARY......Page 123 Exercises......Page 125 2 Devices, Machines, and Programs......Page 126 2.1 REPRESENTING PROBLEMS......Page 127 2.2 DEVICES......Page 130 Exercises......Page 131 2.3 MACHINES......Page 132 2.4 INSTRUCTIONS......Page 133 2.5 INITIALIZERS AND TERMINATORS......Page 135 2.6 PROGRAMS......Page 141 Exercises......Page 145 2.7 RUNNING A PROGRAM......Page 147 2.7.1 Computations, Traces, and Histories......Page 148 2.7.2 Infinite Computations, Traces, and Histories......Page 151 2.8 DETERMINISM AND BLOCKING......Page 154 2.9.1 Acceptors......Page 157 2.9.2 Recognizers......Page 159 2.9.3 Transducers......Page 161 Exercises......Page 164 Exercises......Page 166 3 Simulation......Page 168 3.1 SIMULATION OF PROGRAMS......Page 170 3.2 LOCKSTEP SIMULATION......Page 171 3.2.1 One Control Simulates Two Controls (Pairing Construction)......Page 181 3.3 SIMULATION VIA SUB PROGRAMS......Page 189 3.3.1 Eliminating the NONZERO Test from an Unsigned Counter......Page 195 Exercises......Page 198 3.3.2 An Unsigned Counter Simulates a Signed Counter......Page 199 Exercises......Page 203 3.3.3 Eliminating the EMPTY Test from a Stack......Page 205 3.4 STANDARDIZATION......Page 209 3.4.1 Factoring Programs......Page 210 3.4.2 Eliminating the New Operations and Redundant Tests......Page 215 Exercises......Page 218 3.4.3 Eliminating Dead States and Unreachable States......Page 219 Exercises......Page 221 3.4.4 Eliminating Null Instructions......Page 223 Exercises......Page 226 3.4.5 Cleaning Up and Eliminating Blocking......Page 227 3.5 CHAPTER SUMMARY......Page 229 Exercises......Page 230 4 Finite Machines and Regular Languages......Page 232 4.1 STANDARDIZING FINITE MACHINE PROGRAMS......Page 234 4.2 REGULAR EXPRESSIONS AND LANGUAGES......Page 235 Exercises......Page 237 4.3 REGULAR EXPRESSIONS IN THE REAL WORLD: EGREP......Page 240 4.4 KLEENE'S THEOREM......Page 244 4.4.1 Algorithms for Computing Regular Sets of Paths......Page 247 4.4.2 NFA Languages Are Regular Languages......Page 253 4.4.3 Pencil-and-Paper Algorithm......Page 255 Exercises......Page 260 4.5 NFA LANGUAGES ARE THE SAME AS REGULAR LANGUAGES......Page 262 Exercises......Page 263 4.6 EQUIVALENCE OF NFAs AND DFAs......Page 265 Exercises......Page 269 4.7 MINIMIZING DFRs......Page 273 Exercises......Page 279 4.7.1 Determining Equivalent States......Page 282 Exercises......Page 291 4.8 CLOSURE PROPERTIES......Page 294 4.8.1 Closure under Finite Transductions......Page 296 4.8.2 Composition Theorem......Page 299 Exercises......Page 304 4.9 PUMPING THEOREMS FOR REGULAR LANGUAGES......Page 308 4.9.1 Al and Izzy Pump Strings......Page 314 Exercises......Page 318 4.10 CHAPTER SUMMARY......Page 321 Exercises......Page 322 5 Context-Free Languages......Page 328 5.1 DEFINING LANGUAGES AS SOLUTIONS TO EQUATIONS......Page 329 Exercises......Page 336 5.2 EXISTENCE OF UNIQUE MINIMAL SOLUTIONS......Page 337 Exercises......Page 341 5.3 CFGS AND THEIR STANDARDIZATIONS......Page 344 Exercises......Page 351 5.4 PARSE TREES......Page 354 Exercises......Page 356 5.5 DERIVATIONS......Page 357 Exercises......Page 361 5.6 CFLS ARE THE SAME AS NSA LANGUAGES......Page 362 Exercises......Page 368 5.7 THE CHOMSKY HIERARCHY......Page 369 Exercises......Page 370 5.8 PUMPING THEOREMS FOR CFLS......Page 371 Exercises......Page 381 5.9 AMBIGUITY......Page 384 Exercises......Page 389 5.10 GREIBACH NORMAL FORM......Page 390 Exercises......Page 403 5.11 CYK PARSING ALGORITHM......Page 404 5.12 EARLEY'S PARSING ALGORITHM......Page 406 Exercises......Page 414 Exercises......Page 415 6 Stack and Counter Machines......Page 416 6.1 CLOSURE PROPERTIES......Page 417 Exercises......Page 420 6.2.1 Eliminating PUSH-POP Pairs from DSAs......Page 422 Exercises......Page 423 6.2.2 Making DSAs Halt......Page 425 Exercises......Page 428 6.3 UNAMBIGUOUS PROGRAMS......Page 429 6.4 ON-LINE RECOGNITION......Page 433 Exercises......Page 440 6.5 TWO COUNTERS SIMULATE A STACK......Page 442 Exercises......Page 449 6.6 TWO COUNTERS SIMULATE ANY NUMBER OF COUNTERS......Page 450 6.7 COUNTER LANGUAGES AND PREFIX EQUIVALENCE......Page 452 Exercises......Page 455 6.8 CHAPTER SUMMARY......Page 456 Exercises......Page 457 7 Computability......Page 458 7.1 TAPES AND TURING MACHINES......Page 460 7.1.1 One Tape Simulates k Tapes......Page 462 Exercises......Page 465 7.1.2 Two Stacks Simulate a Tape......Page 466 Exercises......Page 468 7.2 PUTTING THE ARGUMENT ON A TAPE, STACK, OR COUNTER......Page 469 7.3 RANDOM ACCESS MEMORY......Page 471 7.4 UNIVERSAL TURING MACHINE PROGRAM......Page 473 7.5 HERBRAND-GODEL COMPUTABILITY......Page 476 Exercises......Page 480 7.6 RECURSIVE AND RECURSIVELY ENUMERABLE SETS......Page 482 Exercises......Page 491 7.7 THE HALTING PROBLEM......Page 493 Exercises......Page 495 7.8 DIAGONALIZATION......Page 496 7.8.1 The Real Numbers Are Uncountable......Page 497 Exercises......Page 498 7.8.2 Recursively Inseparable Sets......Page 501 Exercises......Page 503 7.8.3 The Total Recursive Functions Cannot Be Enumerated Exactly......Page 504 7.9 MANY-ONE REDUCTIONS......Page 505 Exercises......Page 512 7.10 REWRITING SYSTEMS AND WORD PROBLEMS......Page 513 Exercises......Page 521 7.11 THE POST CORRESPONDENCE PROBLEM......Page 523 Exercises......Page 533 7.12 UNDECIDABILITY OF FIRST-ORDER LOGIC......Page 535 7.13 VALID AND INVALID COMPUTATIONS......Page 542 Exercises......Page 550 7.14 DIOPHANTINE AND EXPONENTIAL DIOPHANTINE EQUATIONS......Page 552 Exercises......Page 555 7.14.1 Some Diophantine and Exponential Diophantine Relations......Page 556 Exercises......Page 559 7.14.2 Arithmetization of 3-Counter Machine Programs......Page 561 Exercises......Page 566 Exercises......Page 568 8 Recursion Theory......Page 571 8.1 RICE'S THEOREM......Page 572 Exercises......Page 575 8.2 THE RECURSION THEOREM AND THE FIXED-POINT THEOREM......Page 577 Exercises......Page 581 8.3 GODEL'S INCOMPLETENESS THEOREM......Page 583 Exercises......Page 587 8.4 ORACLES AND TURING REDUCTIONS......Page 588 8.4.1 Representational Issues......Page 591 8.4.2 Relativization......Page 592 8.4.3 Jumps......Page 594 Exercises......Page 595 8.5 ARITHMETICAL HIERARCHY......Page 596 Exercises......Page 610 8.6 CHAPTER SUMMARY......Page 612 Exercises......Page 613 9 Feasible and Infeasible Problems......Page 615 9.1 TIME-BOUNDED COMPUTATION: P AND NP......Page 616 Exercises......Page 620 9.2 NP-COMPLETENESS......Page 625 Exercises......Page 629 9.3 SEARCH AND OPTIMIZATION VS . DECISION......Page 630 Exercises......Page 632 9.4 CANONICAL NP-COMPLETE PROBLEMS......Page 635 9.5 SYMBOL SYSTEMS......Page 638 Exercises......Page 644 9.6 BOOLEAN FORMULA SATISFIABILITY......Page 645 Exercises......Page 651 9.7 NP-COMPLETE GRAPH PROBLEMS......Page 653 Exercises......Page 662 9.8 NP-COMPLETE PROBLEMS INVOLVING SETS, VECTORS, AND NUMBERS......Page 667 Exercises......Page 675 9.9 AN NP-COMPLETE PROBLEM ABOUT DFRS......Page 678 Exercises......Page 682 9.10 COMPLEXITY OF SOME PROBLEMS INVOLVING REGULAR LANGUAGES......Page 684 Exercises......Page 690 9.11 CHAPTER SUMMARY......Page 693 10.1 GREEK SYMBOLS......Page 695 10.2 GLOSSARY......Page 698 10.3 COMMON ACRONYMS......Page 701 10.4 PROGRAM AND GRAMMAR EQUIVALENCES......Page 704 10.5 HIERARCHY OF PARTIAL FUNCTIONS......Page 706 10.6 HIERARCHY OF RELATIONS......Page 708 10.7 CLOSURE PROPERTIES FOR LANGUAGE CLASSES......Page 709 10.8 DECISION PROBLEMS FOR LANGUAGE CLASSES......Page 710 INDEX......Page 711