catenation, Cycle, of a language, Derivative, Difference, of languages, Homomorphism, Init, of a language. Intersection, Inverse homomorphism. Max, of a language, Min, of a language. Partial-removal operation, Permutation, of a language. Quotient, Reversal, Shuffle, of languages. Substitution, Union

See Conjunctive normal form Cobham, A. 468 Cocke, J. 298, 304 Code, for Turing machine 369-370 Coloring problem 462-463 Commutative law 114-115 Complementation 132-133, 289,375-

377, 388, 426 Composite number 499 Computer 315, 355-363 Concatenation 30,84,86-87,95,104,

115-116,199,284, 382,425-

Conclusion 6

Conjunctive normal form 436

See also CSAT Co-AfV 469-472, 508 Contaimnent, of languages 408 Context-free grammar 4, 169-181,

237-245, 294-296 Context-free language 177, 249 Contradiction, proof by 16-17 Contrapositive 14-16 Converse 16 Cook, S. C. 1, 424, 468 Cooks theorem 428-434 Co-nV 496 Countable set 310 Counter machine 351-354 Counterexample 17-19 Cryptography 470, 499-500 CSAT 436-445, 462

Curamutative law 14

Cycle, of a language 148, 292

CYK algorithm 298-301

Dead state 67 Decidability 5

See also Undecidable problem Decision property

See Emptiness test. Equivalence, of languages. Membership test

Deductive proof 6-17 S

See TVansition function

See Extended transition function

Derivation 174-175,184,190-191

See also Leftmost derivation. Rightmost derivation Derivative 146 Descendant 182

Deterministic finite automaton 45-55, 60-64, 67, 70-72, 79, 91-101, 150-151

Deterministic pushdown automaton 246-251

See Deterministic finite automaton

See Directed Hamilton-circuit problem Diagonalization 368, 370-372 Difference, of languages 137, 289 Digit 109

Directed Hamilton-circuit problem

453-459, 462 Distinguishable states 154, 157 Distributive law 14, 115-116 Document type definition

See DTD Dominating-set problem 465 Dot 108

See aJso Concatenation DPDA

See Deterministic pushdown automaton DTD 169, 192, 199-204 Dynamic progranmiing 298

Edge-cover problem 465 Electronic money 38 Emptiness test 151-152, 296-298 Empty language 31,86, 95,102,115,

117,384-387 Empty stack

See Acceptance by empty stack Empty string 29, 86, 102, 115, 117 Endmarker 352, 354 SSo e

See Empty string e-closure 75

e-NFA 72-80, 96, 101-105, 151 e-production 255, 259-262 e-transition 72, 77-78, 219 Equivalence, of boolean expressions 437

Equivalence, of languages 157-159,

302, 407-408 Equivalence, of regular expressions

117-120 Equivalence, of sets 14, 16 Equivalence, of states 154-157 Even, S. 510 Evey, J. 253

Exact-cover problem 465 Exponential time 415 Exponentiation 503-504 Expression

See Arithmetic expression. Regular expression Extended transition function 49-52,

54, 58-59, 76-77 Extensible markup language

See XML

Factor 209

Factorization 499, 505 False positive/negative 495 Fermats last theorem 309 Final state

See Acceptance by final state. Accepting state Finite automaton 2, 37-45, 90, 228, 315

See also Deterministic finite automaton Finite control

See State Finite set 8-9, 339 Firehouse problem 465 Fischer, R 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 grammar, LR(fc) grammar, Right-hnear grammar Graph, of a function 328 Greibach normal form 271-273 Greibach, S. A. 304 Grep 110, 123 Gross, M. 217

Half, of a language

See Partial-removal operation Halting, of a Turing machine 327-328, 380

Hamilton-circuit problem 419-420,

453, 460-462 See also Directed Hamilton-circuit

problem 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 139-140, 285, 382

See also Inverse homomorphism Hopcroft, J. E. 166, 510 HTML 196-198 Huffman, D. A. 81, 166 Hypothesis 6

See Instantaneous description Idempotent law 116-117 Identity 95, 115 K-and-only-if proof 11-13, 179 If-else structure 193-194 Incompleteness theorem 317-318 Independent-set problem 448-452,462 Induction principle 20 Inductive proof 19-28 Inductive step 19, 22-23 Infinite set 9

Inherently ambiguous language 212-

214,302 bit, of a language 147, 291 Initial state

See Start state Input symbol 46, 57, 222, 227, 318-

319, 327

Instantaneous description 224-227,

320-321 Instruction cycle 359-360 Integer 22

Interior node 181-182 Intersection 14, 121, 134-137, 285-288, 302, 382, 407-408

Intractable problem 1-2,5,361, 413-414

See also NP-complete problem Inverse homomorphism 140-143,289-291, 382, 425-426

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, J. B. Jr. 416 Kruskals algorithm 416

Language 14, 30-31, 33, 52, 59, 149, 177,229-231,326-327,490-492

See also Context-free language. Empty language. Inherently ambiguous language. Recursive language. Recursively enumerable language. Regular language. Universal language

Las-Vegas Turing machine 495 Leaf 181-182

Leftmost derivation 175-177, 184,

187-189, 211-212 Left-sentential form 184, 187-189,

237-238 Length, of a string 29 Lesk, M. 123 Levin, L. A. 468 Lewis, P. M. II 510