Ex Libris                        Wanted                           
blank

       
blank

blank
blank
blank
blank
Hopcroft J.E., Motwani R., Ullman J.D. Introduction to Automata Theory, Languages, and Computation
Hopcroft J.E., Motwani R., Ullman J.D.  Introduction to Automata Theory, Languages, and Computation









?
Ctrl+Enter


: Introduction to Automata Theory, Languages, and Computation

: Hopcroft J.E., Motwani R., Ullman J.D.

:

This book is a rigorous exposition of formal languages and models of computation, with an introduction to computational complexity. The authors present the theory in a concise and straightforward manner, with an eye out for the practical applications. Exercises at the end of each chapter, including some that have been solved, help readers confirm and enhance their understanding of the material. This book is appropriate for upper-level computer science undergraduates who are comfortable with mathematical arguments.


: en

: Computer science//

:

ed2k: ed2k stats

: second edition

: 2001

: 521

: 18.11.2005

: | | ID
blank
$\Delta$      see Transition function
$\epsilon$      see Empty string
$\epsilon$-closure      75
$\epsilon$-NFA      7280 96 101105 151
$\epsilon$-production      255 259262
$\epsilon$-transition      72 7778 219
$\hat{\delta}$      see Extended transition function
$\mathcal{NPS}$      473 477478
$\mathcal{NP}$      419 423 426 470 479 497498 505508
$\mathcal{PS}$      469 473 477479
$\mathcal{P}$      414 423 425426 479 497
$\mathcal{RP}$      469470 488 492498 504
$\mathcal{ZPP}$      469470 488 495497
$\sum$      see Input symbol
2SAT      437 446
3SAT      435436 445446 462
Acceptance by empty stack      230235 249250
Acceptance by final state      229235 249250
Accepting state      46 57 222 319
Accessible state      45
Ackermann's function      381
Address, of memory      357358
Adelman, L.      499 511
Aho, A.V.      35 123 217
Algebra      8586 114120
Algorithm      see Recursive language
Alphabet      2829 132
Alphabetic character      109
Alphanumeric character      109
Alt, of languages      147 292
Ambiguous grammar      205212 249251 302 404406
Ancestor      182
Annihilator      95 115
Arithmetic expression      2326 208210
Associative law      114115
Automaton      2628 (see also Counter machine Deterministic Finite Nondeterministic Pushdown Stack Turing
Backus, J.W.      217
Balanced parentheses      192193
Bar-Hillel, Y.      166 304 411
Basis      19 2223
BLANK      318319 346
Block, of a partition      161
body      171
Boolean expression      426428 436
Borosh, I.I.      468
Bottom-of-tack marker      351
Cantor, D.C.      217 411
CFG      see Context-free grammar
CFL      see Context-free language
Character class      108
Child      182
Chomsky normal form      266269 295296
Chomsky, N.      1 191 217 266 411
Church Turing thesis      318
Church, A.      318 366
Clause      436
Clique problem      462 465
Closure      85 87 104 109 117 199 284 382 425426
Closure property      131 (see also Alt of Closure Complementation Concatenation Cycle of Derivative Difference of Homomorphism Init of Intersection Inverse Max of Min of Partial-removal Permutation of Quotient Reversal Shuffle of Substitution Union)
CNF      see Conjunctive normal form
Co-$\mathcal{NP}$      469472 508
Co-$\mathcal{RP}$      496
Cobham, A.      468
Cocke, J.      298 304
Code, for Turing machine      369370
Coloring problem      462463
Commutative law      114115
Complementation      132133 289 375377 388 426
Composite number      499
Computer      315 355363
Concatenation      30 84 8687 95 104 115116 199 284 382 425426
Conclusion      6
Conjunctive normal form      436 (see also CSAT)
Containment, of languages      408
Context-free grammar      4 169181 237245 294296
Context-free language      177 249
Contradiction, proof by      1617
Contrapositive      1416
CONVERSE      16
Cook's theorem      428434
Cook, S.C.      1 424 468
Countable set      310
Counter machine      351354
Counterexample      1719
Cryptography      470 499500
CSAT      436445 462
Cummutative law      14
Cycle, of a language      148 292
CYK algorithm      298301
dead state      67
Decidability      5 (see also Undecidable problem)
Decision property      see Emptiness test Equivalence of Membership
Deductive proof      617
Derivation      174175 184 190191 Rightmost
Derivative      146
Descendant      182
Deterministic finite automaton      4555 6064 67 7072 79 91101 150151
Deterministic pushdown automaton      246251
DFA      see Deterministic finite automaton
DHC      see Directed Hamilton-circuit problem
Diagonalization      368 370372
Difference, of languages      137 289
digit      109
Directed Hamilton-circuit problem      453459 462
Distinguishable states      154 157
Distributive law      14 115116
Document Type Definition      see DTD
Dominating-set problem      465
Dot      108 (see also Concatenation)
DPDA      see Deterministic pushdown automaton
DTD      169 192 199204
Dynamic programming      298
Edge-cover problem      465
Electronic money      38
Emptiness test      151152 296298
Empty language      31 86 95 102 115 117 384387
Empty stack      see Acceptance by empty stack
Empty string      29 86 102 115 117
Endmarker      352 354355
Equivalence, of boolean expressions      437
Equivalence, of languages      157159 302 407408
Equivalence, of regular expressions      117120
Equivalence, of sets      14 16
Equivalence, of states      154157
Even, S.      510
Every, J.      253
Exact-cover problem      465
Exponential time      415
exponentiation      503504
Expression      see Arithmetic expression Regular
Extended transition function      4952 54 5859 7677
Extensible Markup Language      see XML
Factor      209
Factorization      499 505
False positive/negative      495
Fermat's last theorem      309
Final state      see Acceptance by final state Accepting
Finite automaton      24 3745 90 228 315
Finite control      see State
Finite set      89 339
Firehouse problem      465
Fischer, P.C.      253 366
Floyd, R.W.      217 411
For all      see Quantifier
Garey, M.R.      468
Generating symbol      256 258
Ginsburg, S.      166 304 411
Gischer, J.L.      123
givens      see Hypothesis
Godel, K.      317 366
Grammar      see Ambiguous grammar Context-free LR(k) Right-linear
Graph, of a function      328
Grcibach normal form      271273
Greibach, S.A.      304
grep      110 123
Gross, M.      217
Half, of a language      see Partial-removal operation
Halting, of a Turing machine      327328 380
Hamilton-circuit problem      419420 453 460462
Hamilton-path problem      466
Hartmanis, J.      167 366 468 510
HC      see Hamilton-circuit problem
head      171
Hilbert, D.      317
Hochbaum, D.S.      468
Homomorphism      139140 285 382
Hopcroft, J.E.      166 510
HTML      196198
Huffman, D.A.      81 166
Hypothesis      6
id      see Instantaneous description
Idempotent law      116117
Identity      95 115
If-and-only-if proof      1113 179
If-else structure      193194
Incompleteness theorem      317318
Independent-set problem      448452 462
Induction principle      20
Inductive proof      1928
Inductive step      19 2223
Infinite set      9
Inherently ambiguous language      212214 302
Init, of a language      147 291
Initial state      see Start state
Input symbol      46 57 222 227 318319 327
Instantaneous description      224227 320321
Instruction cycle      359360
INTEGER      22
Interior node      181182
Intersection      14 121 134137 285288 302 382 407408
Intractable problem      12 5 361 413414
Inverse homomorphism      140143 289291 382 425426
IS      see Independent-set problem
Johnson, D.S.      468
Karp, R.M.      424 452 468 510
Kasami, T.      298 304
Kernighan, B.      308
Kleene closure      see Closure
Kleene, S.C.      123 166 366
Knapsack problem      465
Knuth, D.E.      253 488 510
Kruskal's algorithm      416
Kruskal, J.B.Jr.      416
Language      14 3031 33 52 59 149 177 229231 326327 490492 Empty Inherently Recursive Recursively Regular Universal
Las-Vegas Turing machine      495
Leaf      181182
Left-sentential form      184 187189 237238
Leftmost derivation      175177 184 187189 211212
Length, of a string      29
Lesk, M.      123
Levin, L.A.      468
Lewis, P.M.      11 510
Lex      110111 123
Lexical analyzer      2 84 109111
Linear integer programming problem      465
Literal      436
LR(k) grammar      253
markup language      see HTML XML
Max, of a language      147 292
McCarthy, J.      81
McCulloch, W.S.      81
McNaughton, R.      123 167
Mealy, G.H.      81
Membership test      153 298301
Miller, G.L.      510
Min, of a language      147 292
Minimization, of DFA's      159164
Minimum-weight spanning tree      415416
Minsky, M.L.      366 411
Modified Post's correspondence problem      394402
Modular arithmetic      501503
modus ponens      7
Monte-carlo Turing machine      493
Moore's law      1
Moore, E.F.      81 167
Motwani, R.      510
Move      see Transition function
Multihead Turing machine      344
Multiple tracks      see Track
Multiplication      362 501503
Multistack machine      see Stack machine
Multitape Turing machine      336340
Mutual induction      2628
Natural language      191
Naur, P.      217
NC      see Node-cover problem
NFA      see Nondeterministic finite automaton
Node-cover problem      452453 462
Nondeterministic finite automaton      5570 96 150151 163
Nondeterministic polynomial space      see $\mathcal{NPS}$
Nondeterministic polynomial time      see $\mathcal{NP}$
Nondeterministic Turing machine      340342 473 476478 493
Nonrecursive language      see Undecidable problem
Nonrecursively enumerable language      see Recursively enumerable language
Nonterminal      see Variable
Normal form      255273
NP-complete problem      422 424 447 450 470472 Coloring CSAT Dominating-set Edge-cover Exact-cover Firehouse Hamilton-circuit Hamilton-path Independent-set Knapsack Linear Node-cover Satisfiability Subgraph 3SAT Traveling Unit-execution-time-scheduling
NP-hard problem      423 (see also Intractable problem)
Nullable symbol      259260 298
Observation      17
Oettinger, A.G.      253
Ogden's lemma      281
Ogden, W.      304
Palindrome      170 177178
Papadimitriou, C.H.      510
Parent      182
Parse tree      181189 207 274275
Parser      169 192195
Partial function      329
Partial solution, to PCP      395
Partial-removal operation      147 292
Partition      161
Paull, M.C.      304
PCP      see Post's correspondence problem
PDA      see Pushdown automaton
Perles, M.      166 304 411
Permutation, of a language      293
Pigeonhole Principle      66
Pitts, W.      81
Polynomial space      469 473478
Polynomial time      5 (see also $\mathcal{P}$
Polynomial-time reduction      413414 421423 478479
pop      220
Post's correspondence problem      392402
Post, E.      366 411
Pratt, V.R.      510
Precedence, of operators      8889 208
prefix property      248249
Prime number      470 498508
Problem      3133 417
Product construction      134
Production      171 (see also $\epsilon$-production Unit
proof      56 12 proof Deductive If-and-only-if Inductive
Property, of languages      387388
Protocol      2 3945
PS-complete problem      478479 (see also Quantified boolean formula Shannon
Public-key signature      500501
Pumping lemma      126130 274281
push      220
Pushdown automaton      219246 294295 Stack
1 2
blank
blank
blank
HR
@Mail.ru
       © , 2004-2017
   | Valid HTML 4.01! | Valid CSS!