Introduction to computer theory / (Record no. 1926)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 04005cam a2200169 a 4500 |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 0471510106 |
| 040 ## - CATALOGING SOURCE | |
| Transcribing agency | CUS |
| 082 00 - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 004 |
| Item number | COH/I |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Cohen, Daniel I. A., |
| 245 10 - TITLE STATEMENT | |
| Title | Introduction to computer theory / |
| Statement of responsibility, etc. | Daniel I.A. Cohen. |
| 250 ## - EDITION STATEMENT | |
| Edition statement | 2nd ed. |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Place of publication, distribution, etc. | New York : |
| Name of publisher, distributor, etc. | Wiley, |
| Date of publication, distribution, etc. | 1991. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | xii, 838 p. : |
| Dimensions | 25 cm. |
| 505 ## - FORMATTED CONTENTS NOTE | |
| Formatted contents note | PART I AUTOMATA THEORY<br/>1 Background<br/>2 Languages<br/>Languages in the Abstract 7<br/>Introduction to Defining Languages 10<br/>Kieene Closure 14<br/>Problems 19<br/>3 Recursive Definitions<br/>A New Method for Defining Languages 21<br/>An Important Language: Arithemetic Expressions 25<br/>Problems 28<br/>4 Regular Expressions<br/>Defining Languages by Another New Method 31<br/>Formal Definition of Regular Expressions 35<br/>Languages Associated with Regular Expressions 43<br/>Finite Languages Are Regular 44<br/>How Hard It Is To Understand a Regular Expression 45<br/>Introducing EVEN-EVEN 48<br/>Problems 49<br/>5 Finite Automata<br/>Yet Another Method for Defining Languages 52<br/>FAs and Their Languages 59<br/>EVEN-EVEN Revisited 69<br/>Problems 71<br/>6 IVansition Graphs<br/>Relaxing the Restriction on Inputs 76<br/>Looking at TGs 81<br/>Generalized Transition Graphs 86<br/>Nondeterminism 87<br/>Problems 88<br/>7 Kleene's Theorem<br/>Unification 92<br/>Tuming TGs into Regular Expressions 93<br/>Converting Regular Expressions into FAs 108<br/>Nondeterministic Finite Automata 135<br/>NFAs and Kleene's Theorem 140<br/>Problems 142<br/>8 Finite Automata with Output<br/>Moore Machines 149<br/>Mealy Machines 152<br/>Moore = Mealy 156<br/>Transducers as Models of Sequential Circuits 161<br/>Problems 164<br/>9 Regular Languages<br/>Closure Properties 169<br/>Complements and Intersections 172<br/>Problems 185<br/>10 Nonregular Languages<br/>The Pumping Lemma 187<br/>The Myhill - Nerode Theorem 196<br/>Quotient Languages 200<br/>Problems 203<br/>11 Decidability<br/>Equivalence 207<br/>Finiteness 214<br/>Problems 217<br/>PART II PUSHDOWN AUTOMATA THEORY<br/>12 Context-Free Grammars<br/>Syntax as a Method for Defining Languages 224<br/>Symbolism for Generative Grammars 230<br/>Trees 241<br/>Lukasiewicz Notation 245<br/>Ambiguity 250<br/>The Total Language Tree 252<br/>Problems 254<br/>13 Grammatical Format<br/>Regular Grammars 259<br/>Killing A-Productions 265<br/>Killing Unit Productions 272<br/>Chomsky Normal Form 275<br/>Leftmost Derivations 282<br/>Problems 285<br/>14 Pushdown Automata<br/>A New Fcirnat for FAs 289<br/>Adding a Pushdown Stack 293<br/>Defining the PDA 307<br/>Problems 312<br/>15 CFG = PDA<br/>Building a PDA for Every CFG 318<br/>Building a CFG for Every PDA 327<br/>Problems 348<br/>16 Non-Context-Free Languages<br/>Self-Embeddedness 351<br/>The Pumping Lemma for CFLs 360<br/>Problems 373<br/>17 Context-Free Languages<br/>Closure Properties 376<br/>Intersection and Complement 385<br/>Mixing Context-Free and Regular Languages 393<br/>Problems 398<br/>18 Decidability<br/>Emptiness and Uselessness 402<br/>Finiteness 408<br/>Membership—The CYK Algorithm 410<br/>Parsing Simple Arithmetic 415<br/>Problems 429<br/>19 Ttiring Machines<br/>PART III TURING THEORY<br/>The Turing Machine 434<br/>The Subprogram INSERT 449<br/>The Subprogram DELETE 452<br/>Problems 454<br/>20 Post Machines<br/>The Post Machine 457<br/>Simulating a PM on a TM 462<br/>Simulating a TM on a PM 468<br/>Problems 477<br/>21 Minsky's Theorem<br/>The Two-Stack PDA 480<br/>Just Another TM 482<br/>Problems 492<br/>22 Variations on the TM<br/>The Move-in-State Machine 494<br/>The Stay-Option Machine 499<br/>The^-TrackTM 502<br/>The Two-Way Infinite Tape Model 511<br/>The Nondeterministic TM 518<br/>The Read-only TM 524<br/>Problems 531<br/>23 TM Languages<br/>Recursively Enumerable Languages 535<br/>The Encoding of Turing Machines 545<br/>A Non-Recursively Enumerable Language 549<br/>The Universal Turing Machine 552<br/>Not All r.e. Languages Are Recursive 557<br/>Decidability 558<br/>Problems 562<br/>24 The Chomsky Hierarchy<br/>Phrase-Structure Grammars 565<br/>TypeO = TM 574<br/>The Product and Kleene Closure of r.e. Languages 586<br/>Context-Sensitive Grammars 588<br/>Problems 590<br/>25 Computers<br/>Defining the Computer 594<br/>Computable Functions 599<br/>Church's Thesis 610<br/>TMs as Language Generators 612<br/>Problems 616 |
| 650 #0 - SUBJECT | |
| Keyword | Electronic Digital Computers. |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | General Books |
| Withdrawn status | Lost status | Damaged status | Not for loan | Home library | Current library | Shelving location | Date acquired | Full call number | Accession number | Date last seen | Date last checked out | Koha item type |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Central Library, Sikkim University | Central Library, Sikkim University | General Book Section | 01/06/2016 | 004 COH/I | P31943 | 14/07/2018 | 14/07/2018 | General Books |