420 ~ Index
Decision algorithms (see Context-free grammar)
Derivation, 110, 111
leftmost, 187
rightmost, 187
Derivation tree (parse tree), 181. 184
definition of, 181
subtree of, 182
yield of, 182
Descendant, 51
Deterministic
finite automaton, 73
pda, 236
Directed graph (or digraph), 47
Dirichlet drawer principle, 46
Disjunction (OR), 3
Disjunctive nonnal fonn, 11
Distributivity, 39
Elementary product, 11
Equivalence
class, 42
of DFA and NDFA, 80--84
of finite automata, 157, 158
of regular expressions, 160
relation, 41
of states, 91
of well-fonned fonnulas, 9
Euclidean algorithm, 349
Fibonacci numbers, 69
Field, 39
Final state, 73, 74, 77
Finite automaton
deterrrtinistic, 73
minimization of, 91-97
nondeterministic, 78
and regular expression, 153
Function (or map), 45
by minimization, 330
partial, 322
by recursion, 328
total, 322
GOdel, Kurt, 332
Grammar, 109
monotonic, 121
self-embedding, 226
Graph,47
connected, 49
representation, 47
Greibach nonnal fonn (see Nonnal fonn)
Group, 38
Growth rate of functions, 346
Halting problem of Turing machine,
314-315
Hamiltonian circuit problem, 359
Handle production, 268
Hierarchy of languages, 120--122
ID (Instantaneous description)
of pushdown automaton, 229
of Turing machine, 279
Identities
logical, 10
for regular expressions, 138
Identity element, 38, 55
If and only if, 4
Implication (IF,,,THEN,,,), 4
Inclusion relation, 123
Initial function, 323
Induction, 57, 58, 60
Initial state, 73-74, 78, 228, 278
Internal vertex, 50
Inverse, 38
Kleene's theorem, 142
A-move, 140
elimination of, 141
Language(s)
and automaton, 128
classification of, 120
generated by a grammar, 110
Leaf of a tree, 50
Length
of path, 51
of string, 55
Levi's theorem, 56
Linear bounded automaton (LBA), 297-299,
301-303
and languages, 299-301
Logical connectives (see Connectives)
LR(k) graJlh'TIar, 267