c H a p t e R 9 review
teRminology
addition modulo n (p. 692)
alphabet (pp. 694, 782)
alternating group (p. 701)
associative binary operation
(p. 687)
Backus Naur form (BNF) (p. 787)
bottom-up parsing (p. 794)
cancellation laws (p. 696)
canonical parity-check matrix
(p. 721)
check bits in a code word (p. 721)
Chomsky hierarchy (p. 790)
coefficient (p. 690)
commutative binary operation
(p. 687)
commutative group (p. 688)
concatenation (p. 694)
context-free (type 2) grammar
(p. 790)
context-free language (p. 790)
context-sensitive (type 1)
grammar (p. 790)
context-sensitive language
(p. 790)
coset leader (p. 723)
cosets of a subgroup in a group
(p. 717)
decision problem (p. 772)
degree of a polynomial (p. 691)
delay element (p. 744)
direct generation (derivation) of a
word (p. 784)
double-error detecting code
(p. 715)
empty string (p. 694)
equivalent grammars (p. 791)
equivalent states (p. 739)
erasing convention (p. 789)
even and odd permutations
(p. 700)
final state (pp. 734, 765)
finite-state machine (p. 729)
formal language (p. 785)
free monoid generated by a set A
(p. 695)
generation (derivation) of a word
(p. 784)
group (p. 688)
group code (p. 719)
group of permutations on a set A
(p. 693)
halting problem (p. 774)
Hamming distance (p. 718)
homomorphism (p. 702)
identity element (p. 687)
improper subgroup (p. 700)
information bits in a code word
(p. 721)
input alphabet (p. 729)
intractable problem (p. 776)
inverse element (p. 687)
isomorphism (p. 702)
k-equivalent states (p. 739)
kernel of a homomorphism
(p. 716)
language (p. 782)
language generated by a
grammar G (p. 784)
left cancellation law (p. 696)
left cosets (p. 717)
length of a string (p. 694)
linear bounded automaton (lba)
(p. 792)
maximum likelihood decoding
(p. 715)
minimum distance of a code
(p. 718)
monoid (p. 689)
multiplication modulo n (p. 692)
negative solution to a decision
problem (p. 772)
next-state function (p. 729)
nondeterministic Turing machine
(p. 777)
NP (p. 777)
NP-complete problem (p. 778)
number-theoretic function (p. 767)
order of a group (p. 698)
output alphabet (p. 729)
output function (p. 729)
P (p. 777)
parse tree (p. 793)
partial function (p. 767)
partition refinement (p. 741)
perfect code (p. 722)
permutation group (p. 700)
phrase-structure (type 0) grammar
(p. 783)
polynomial in x with real number
coefficients (polynomial in x
over R) (p. 690)
polynomial of zero degree (p. 691)
positive solution to a decision
problem (p. 772)
production (p.783)
proper subgroup (p. 700)
pushdown automaton (pda)
(p. 792)
recognition by a finite-state
machine (p. 734)
recognition (acceptance) by a
Turing machine (p. 765)
refinement (p.741)
regular expression (p. 735)
regular (type 3) grammar (p. 790)
regular language (p. 790)
regular set (p. 736)
right cancellation law (p. 696)
right cosets (p. 717)
semigroup (p. 689)
semigroup of transformations on a
set A (p. 693)
sequential network (p. 745)
single-error correcting code
(p. 715)
start symbol (p. 783)
state graph (p. 730)
state table (p. 730)
string (p. 694)
subgroup (p. 699)
symbol (p. 694)
symmetric group of degree n
(p. 693)
syndrome of a binary n-tuple in a
group code (p. 724)
Chapter 9 Review
799
teRminology
addition modulo n (p. 692)
alphabet (pp. 694, 782)
alternating group (p. 701)
associative binary operation
(p. 687)
Backus Naur form (BNF) (p. 787)
bottom-up parsing (p. 794)
cancellation laws (p. 696)
canonical parity-check matrix
(p. 721)
check bits in a code word (p. 721)
Chomsky hierarchy (p. 790)
coefficient (p. 690)
commutative binary operation
(p. 687)
commutative group (p. 688)
concatenation (p. 694)
context-free (type 2) grammar
(p. 790)
context-free language (p. 790)
context-sensitive (type 1)
grammar (p. 790)
context-sensitive language
(p. 790)
coset leader (p. 723)
cosets of a subgroup in a group
(p. 717)
decision problem (p. 772)
degree of a polynomial (p. 691)
delay element (p. 744)
direct generation (derivation) of a
word (p. 784)
double-error detecting code
(p. 715)
empty string (p. 694)
equivalent grammars (p. 791)
equivalent states (p. 739)
erasing convention (p. 789)
even and odd permutations
(p. 700)
final state (pp. 734, 765)
finite-state machine (p. 729)
formal language (p. 785)
free monoid generated by a set A
(p. 695)
generation (derivation) of a word
(p. 784)
group (p. 688)
group code (p. 719)
group of permutations on a set A
(p. 693)
halting problem (p. 774)
Hamming distance (p. 718)
homomorphism (p. 702)
identity element (p. 687)
improper subgroup (p. 700)
information bits in a code word
(p. 721)
input alphabet (p. 729)
intractable problem (p. 776)
inverse element (p. 687)
isomorphism (p. 702)
k-equivalent states (p. 739)
kernel of a homomorphism
(p. 716)
language (p. 782)
language generated by a
grammar G (p. 784)
left cancellation law (p. 696)
left cosets (p. 717)
length of a string (p. 694)
linear bounded automaton (lba)
(p. 792)
maximum likelihood decoding
(p. 715)
minimum distance of a code
(p. 718)
monoid (p. 689)
multiplication modulo n (p. 692)
negative solution to a decision
problem (p. 772)
next-state function (p. 729)
nondeterministic Turing machine
(p. 777)
NP (p. 777)
NP-complete problem (p. 778)
number-theoretic function (p. 767)
order of a group (p. 698)
output alphabet (p. 729)
output function (p. 729)
P (p. 777)
parse tree (p. 793)
partial function (p. 767)
partition refinement (p. 741)
perfect code (p. 722)
permutation group (p. 700)
phrase-structure (type 0) grammar
(p. 783)
polynomial in x with real number
coefficients (polynomial in x
over R) (p. 690)
polynomial of zero degree (p. 691)
positive solution to a decision
problem (p. 772)
production (p.783)
proper subgroup (p. 700)
pushdown automaton (pda)
(p. 792)
recognition by a finite-state
machine (p. 734)
recognition (acceptance) by a
Turing machine (p. 765)
refinement (p.741)
regular expression (p. 735)
regular (type 3) grammar (p. 790)
regular language (p. 790)
regular set (p. 736)
right cancellation law (p. 696)
right cosets (p. 717)
semigroup (p. 689)
semigroup of transformations on a
set A (p. 693)
sequential network (p. 745)
single-error correcting code
(p. 715)
start symbol (p. 783)
state graph (p. 730)
state table (p. 730)
string (p. 694)
subgroup (p. 699)
symbol (p. 694)
symmetric group of degree n
(p. 693)
syndrome of a binary n-tuple in a
group code (p. 724)
Chapter 9 Review
799