800
Modeling Arithmetic, Computation, and Languages
tape alphabet (p. 762)
terminal (p. 783)
top-down parsing (p. 794)
total function (p. 767)
transposition (p. 700)
Turing-computable function
(p. 768)
Turing machine (p. 762)
type 0 language (p. 790)
unreachable state (p. 737)
unsolvable (undecidable) decision
problem (p. 772)
vocabulary (p. 782)
weight of a code word (p. 719)
word (pp. 694, 782)
Self-teSt
Answer the following true–false questions.
section 9.1
1. A binary operation is associative if the order of the
elements being operated upon does not matter.
2. The identity i in a group 3G, # 4 has the property that
x
−1 # i = i # x
−1
= x
−1
for all x in G.
3. Every group is also a monoid.
4. A group of order 10 cannot have a subgroup of
order 6.
5. If 3S, # 4 and 3T, + 4 are two groups, then a function
f: S S T for which f (x # y) = f (x) + f ( y) is an
isomorphism.
section 9.2
1. A binary single-error correcting code must have
minimum distance at least 3.
2. In a canonical n × r parity-check matrix H, the
bottom r rows form the r × r identity matrix.
3. A canonical n × r parity-check matrix H maps all
of Z
m
2 to code words in Z
n
2 .
4. If the syndrome of a received word X in Z
n
2 is 0 r ,
then X is assumed to be a code word.
5. A perfect code is “perfect” because no bit errors
will occur during transmission.
section 9.3
1. The next state of a finite-state machine is determined
by its present state and the present input symbol.
2. The set of all binary strings ending in two 0s is
regular.
3. A finite-state machine cannot get to a state from
which there is no exit.
4. According to Kleene’s theorem, a set that cannot be
described by a regular expression cannot be recognized by a finite-state machine.
5. In a finite-state machine, k-equivalent states are
also (k + 1)-equivalent.
section 9.4
1. A Turing machine halts if and only if it enters a
final state.
2. A Turing machine that computes the function
f (n) = n + 1, given input n, will halt with (n + 1)
1s on its tape.
3. Church’s thesis says that the halting problem is
unsolvable.
4. The halting problem says that, given a Turing machine and its input, there is no algorithm to decide
whether the Turing machine halts when run on that
input.
5. A set in P is recognizable by a Turing machine in
no more than a polynomial number of steps.
section 9.5
1. The language generated by a type 0 grammar G is
the set of all strings of terminals generated from the
start symbol by applying G’s productions a finite
number of times.
2. Beginning at the start symbol and applying the
productions of a grammar G eventually leads to a
string of terminals.
3. A language generated by a grammar that is contextsensitive but not context-free is a context-sensitive
but not context-free language.
4. Any regular set is a regular language.
5. A parse tree will have as many leaves as terminal
symbols in the word being derived.
Modeling Arithmetic, Computation, and Languages
tape alphabet (p. 762)
terminal (p. 783)
top-down parsing (p. 794)
total function (p. 767)
transposition (p. 700)
Turing-computable function
(p. 768)
Turing machine (p. 762)
type 0 language (p. 790)
unreachable state (p. 737)
unsolvable (undecidable) decision
problem (p. 772)
vocabulary (p. 782)
weight of a code word (p. 719)
word (pp. 694, 782)
Self-teSt
Answer the following true–false questions.
section 9.1
1. A binary operation is associative if the order of the
elements being operated upon does not matter.
2. The identity i in a group 3G, # 4 has the property that
x
−1 # i = i # x
−1
= x
−1
for all x in G.
3. Every group is also a monoid.
4. A group of order 10 cannot have a subgroup of
order 6.
5. If 3S, # 4 and 3T, + 4 are two groups, then a function
f: S S T for which f (x # y) = f (x) + f ( y) is an
isomorphism.
section 9.2
1. A binary single-error correcting code must have
minimum distance at least 3.
2. In a canonical n × r parity-check matrix H, the
bottom r rows form the r × r identity matrix.
3. A canonical n × r parity-check matrix H maps all
of Z
m
2 to code words in Z
n
2 .
4. If the syndrome of a received word X in Z
n
2 is 0 r ,
then X is assumed to be a code word.
5. A perfect code is “perfect” because no bit errors
will occur during transmission.
section 9.3
1. The next state of a finite-state machine is determined
by its present state and the present input symbol.
2. The set of all binary strings ending in two 0s is
regular.
3. A finite-state machine cannot get to a state from
which there is no exit.
4. According to Kleene’s theorem, a set that cannot be
described by a regular expression cannot be recognized by a finite-state machine.
5. In a finite-state machine, k-equivalent states are
also (k + 1)-equivalent.
section 9.4
1. A Turing machine halts if and only if it enters a
final state.
2. A Turing machine that computes the function
f (n) = n + 1, given input n, will halt with (n + 1)
1s on its tape.
3. Church’s thesis says that the halting problem is
unsolvable.
4. The halting problem says that, given a Turing machine and its input, there is no algorithm to decide
whether the Turing machine halts when run on that
input.
5. A set in P is recognizable by a Turing machine in
no more than a polynomial number of steps.
section 9.5
1. The language generated by a type 0 grammar G is
the set of all strings of terminals generated from the
start symbol by applying G’s productions a finite
number of times.
2. Beginning at the start symbol and applying the
productions of a grammar G eventually leads to a
string of terminals.
3. A language generated by a grammar that is contextsensitive but not context-free is a context-sensitive
but not context-free language.
4. Any regular set is a regular language.
5. A parse tree will have as many leaves as terminal
symbols in the word being derived.