422 );! Index
Regular grammar, 122
Regular sets, 137
closure properties of, 165-167
and regular grammar, 167
Relations
reflexive, 41
symmetric, 41
transitive, 41
Right-linear grammar, 226
Ring, 39
Root, 50
Russels paradox, 320
SAT problem (satisfiability problem), 353
Self-embedding grammar, 226
Semigroup, 38
Sentence, 110
Sentential form, 110
Sets, 36, 37, 38, 39, 40
complement of, 37
intersection of, 37
union of, 37
Simple graph, 70
Start symbol, 109
Statement (see Proposition)
String
empty, 54
length of, 55
operations on, 54
prefix of, 55
suffix of, 55
Strong Church-Turing thesis, 363
Subroutines, 290
Successor, 48
Symmetric difference, 68
Tautology, 8
Time complexity, 294, 349
Top-down parsing, 252
Top-down parsing, using deterministic pda's
256
Transition function, 73, 78, 228
properties of, 75-76
Transition system, 74
containing A-moves, 140
and regular grammar, 169
Transitive closure, 43
Transpose, 55
Travelling salesman problem, 359
Tree. 49
height of, 51
properties of, 49-50
Turing-computable functions, 333
Turing machine, 277
construction of, to compute the projection
function. 336
construction of, to compute the successor
function, 335
construction of, to compute the zero
function, 334
construction of, to pertorm composition,
338
construction of, to perform minimization.
340
construction of, to perform recursion, 339
description of, 289
design of, 284
multiple track, 290
multitape, 292
nondetenninistic, 295
representation by 10, 279
representation by transition diagram, 281
representation by transition table, 280
and type 0 grammar, 299-301
Type 0 grammar (see Grammar)
Type 1 grarmnar (see Context-sensitive
grammar)
Type 2 grammar (see Context-free grammar)
Type 3 grammar (see Regular grammar)
Unambiguous grammar, 271
Undecidable language, 313
Unit production, 199
elimination of, 199-201
Valid
argument, 15
predicate formula, 22
Variable. 109
Vertex, 47
ancestor of. 51
degree of, 48
descendant of, 51
son of. 51
Well-formed formula, 6
or predicate calculus, 21