Introduction to computer theory / Daniel I.A. Cohen.
Material type:
TextPublication details: New York : Wiley, 1991Edition: 2nd edDescription: xii, 838 p. : 25 cmISBN: 0471510106Subject(s): Electronic Digital ComputersDDC classification: 004 | Item type | Current library | Call number | Status | Date due | Barcode | Item holds |
|---|---|---|---|---|---|---|
General Books
|
Central Library, Sikkim University General Book Section | 004 COH/I (Browse shelf(Opens below)) | Available | P31943 |
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
There are no comments on this title.