References And Index

References for Further Reading A. V. Aho and J. D. Ullman, The Theory of Parsing, Translations, and compiling, Vol. 1: Parsing, Englewood Cliffs, N. J.: Prentice-Hall, 1972. P. J. Denning, J. B. Dennis, and J. E. Qualitz, Machine, Languages, and Computation, Englewood Cliffs, N. J.: Prentice Hall, 1978 H. Ehrig, M. Nagl, G. Rozenberg, and A. Rosenbeld (Edition), Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science #291, Springe-Verlag, 1986. M. A. Harrison, Introduction to Formal Language Theory, Reading, Mass.: Addison-Wesley, 1978. J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Second Ed., Addison-Wesley, 2001. P. Linz, An Introduction to Formal Languages and Automata, Third Ed., Jones and Bartlett Publishers, 2001. D. W. Mount, Bioinformatics: Sequence and Genome Analysis, Cold Spring Harbor Lab. Press, 2001. F. P. Preparata and R. T. Yeh, Introduction to Discrete Structures for Computer Science and Engineering, Reading Mass.: Addison-Wesley, 1973. S. Wolfram, Theory and Application of Cellular Automata, World Scientific, 1986.

1

Index 2-D tape TM , 165 2-dimensional(2D)-tape FA , 177 2-head FA, 178 2-sided L-system , 62 2-way FA , 176, 515 2-way PDA , 169 Accept, 81 Accepting by empty stack , 172 Accepting configuration , 370, 383 Accepting state , 94 Algebraic properties, 73 Ambiguous CFG , 294 Amino acid , 428 Associative law, 73 Associativity, 301 Axiom, 63 Base, 15 Bottom of the stack symbol, 101, 104 Bottom-up left-to-right traversal, 356 Bottom-up parsing, 379 CA, 179 Cell, 81

Cellular automata, 179 Characterization, 189, 191, 471 Chomsky hierarchy, 185, 187, 190, 309, 310, 435 Chomsky normal from (CNF), 277, 278 Church's hypothesis, 181 Closure, 5 Closure property, 248 Closure property of DC 리 , 543 Coding region, 430 Codon , 428, 430 Commutative law, 73 Complement , 240 Complementary strand, 426 Composite symbol, 3, 480 Computational capability, 160 Computing regular expression , 532 Concatenate, 2 Conditional connective, 22 Configuration, 360 Constructive proof, 17 Containment, 185, 188, 190, 309, 310 Context-free grammar, 51

2

Index Context-sensitive grammar, 51 Countable, 438 Crossing information (CI), 518 Crossing state pair, 518 CYK algorithm, 352, 533, 569 Declarative statement, 6 DeMorgan's law, 4 Deterministic finite automata (DFA), 111 Deterministic linear bounded automata (DLBA), 98 Deterministic L-system, 62 Deterministic pushdown automata (DPDA), 100 Deterministic Turing machine (DTM), 81 Diagonalization, 21, 453, 465 Distributive law, 73 Document type definition (DTD), 414 Encoding function, 444 Enumerable set, 437 Enumerable languages, 450 Enumeration, 437 Enumerator, 437 epsilon-move, 102 epsilon-transition, 146

Equivalent state, 224 Exclusive OR, 4 Existential quantification, 13, 346 Extensible markup language (XML), 414, 418 FA array, 179 Finite state control, 81 Formal language, 30, 31, 48 Front nonterminal, 280 Front recursion, 280 Gene code, 425 Gene grammar, 425 Genome, 425 Grammar, 30, 33 Greibach normal form (GNF), 277, 280 Hidden Markov model (HMM), 180 Homomorphism, 444 Hyper text markup language (HTML), 414, 415 Hypothesis, 15 Implication, 9 Induction, 15 Induction hypothesis, 15 Inherently ambiguous, 305

3

Index Input alphabet, 94 Intersection, 240 Intron, 427, 430 Kleene closure, 5 Kleene star, 240 Language class, 309 Left associativity, 304 Left linear, 57 Leftmost derivation, 354 Lex, 352, 404 Lexical ambiguity, 288 Lexical analyzer, 404 Linear, 57 LL(k) grammar, 365, 378 Look ahead, 359, 368 Look ahead LR parser (LALR), 406 Look-ahead, 368, 373 LR(k) grammar, 386, 403 LR(k) parser, 379 L-system, 62 Lyndenmayer, 62 Membership test for CFL, 569

Minimize, 224, 226 Moore automata, 161 Morphemes, 49 Move, 81 Multi-head FA , 178 Multi-stack PDA, 170 Multi-tape TM, 164 Multi-track TM, 162 NFA, 126 Non-constructive proof, 17 Nondeterministic algorithm, 143 Nondeterministic automata, 124. 154 Nondeterministic choose, 141 Nondeterministic computing, 140 Nondeterministic finite automata (NFA), 126 Nondeterministic linear bounded automata (NLBA), 139 Nondeterministic pushdown automata (NPDA), 132 Nondeterministic Turing machine (NTM), 139 Non-front terminal, 280 Nonterminal alphabet, 49 Normal from, 277 Normal form of PDA, 544

4

Index Null string, 2 Ogden's lemma, 336 Parallel rewriting, 56, 62 Parse table, 366, 385 Parse tree, 290, 354 Parsing, 352 Pascal syntax flow graph, 508 Path label, 317 Phrase structured grammar, 49 Pigeonhole principle, 18 Pop, 100 Power set, 5 Precedence, 293, 301 Product, 240 Production rule, 54 Proof by cases, 11 Proof by contradiction, 12 Proof by contrapositive, 11 Proof by counting, 20 Proof by example, 13 Proof by generalization, 14 Proof by induction, 15

Proof by pigeonhole principle, 18 Proof technique, 10 Proper containment, 309, 312 Property list, 3 Proposition, 6 Pumping lemma, 316, 322, 564 Pumping lemma for CFL, 328 Purine, 431 Push, 100 Pushdown stack, 100 Pyrimidine, 431 Read only, 100 Recursive language, 460 Recursive TM, 459, 460 Recursively enumerable (R.E.), 50, 446 Reduced DFA, 229 Reduction table, 385 Regular expression, 70 Regular grammar, 52 Reversal, 240 Rewriting rule, 33, 54 Ribosome, 427

5

Index

Right associativity, 304 Right linear, 57 Rightmost derivation, 354 RNA transcription, 426 Rule, 31, 33 Semantic ambiguity, 288 Sentential form, 50 Set complement, 4 Set intersection, 4 Set operation, 4 Set product, 4 Set properties, 3 Set specification, 3 Set subtraction, 4, 240 Set union, 4 Shift-in, 394, 400 Simulate, 448 Splicing, 427 Spontaneous transition, 146 Stack alphabet, 104 Stack head, 101 Stack-top, 100

Stack-top erasing set, 489 Start codon, 428, 430 Start state, 94 Start symbol, 49 State, 81 State minimization, 224 State partitioning technique, 226 State transition function, 82, 92, 94 State transition graph, 82, 90 State transition profile, 126 State transition table, 93 Stop codon, 428, 430 String, 2 Sum-of-subset problem, 142 Symbol, 2 Syntactic ambiguity, 288 Syntactic category, 49 Syntax, 290 Syntax diagram, 67 Syntax flow graph, 67 Tape alphabet, 94 Tape head, 81

6

Index Terminal alphabet, 49 Token definition, 404 Token description, 404 Top-down left-to-right traversal, 355 Total alphabet, 49 Transcribe, 426 Transcript, 429 Transducer, 161 Transition path, 317 Translation, 427 Truth table, 6 Turing machine, 80 Type 0 grammar, 49 Type 1 grammar, 51 Type 2 grammar, 51 Type 3 grammar, 52 Union, 240 Unit production rule, 262, 264 Universal quantification, 13, 346 Universal set, 4 Universal Turing machine, 448 Useless symbol, 266

User-written code, 405, 408 Variable, 40 YACC, 352, 406 Yield, 291

7