o n t H e c o m p u t e R
For Exercises 1–11, write a computer program that
produces the desired output from the given input.
1. Input: Two words from an alphabet A
Output: Their concatenation
2. Input: Positive integer n and finite alphabet A
Output: All words over A of length ≤ n
3. Input: Positive integer n
Output: Tables for addition and multiplication
modulo n
4. Input: Positive integer n
Output: The n! elements of S n expressed both in
array form and in cycle notation, the group table for
3S n , + 4, and the group table for 3A n , + 4
5. Input: n × n array, n ≤ 10, that purports to represent a binary operation on the finite set of integers
from 1 to n
Output: Determination of whether the set under this
operation is a commutative group
6. Input: Two n × n arrays, n ≤ 10, that represent
two groups and an array that represents a function
from the first group to the second
Output: Determination of whether the function is
an isomorphism
7. Input: A canonical n × r parity-check matrix H
for a single-error correcting code with r ≤ 4 and
n ≤ 2
r
−1
Output: The set of binary m-tuples H encodes and
the code word for each one
8. Input: A canonical parity-check matrix for a perfect
single-error correcting code where r ≤ 5 and any
binary n-tuple X
Output: The binary n-tuple to which X is decoded
9. Input: Positive integer n, n ≤ 50, representing the
number of states of a finite-state machine with input alphabet = output alphabet = 50, 16 and an
n × 3 array representing the state table description
of such a machine
Output: List of any states unreachable from the
start state s 0
10. Input: Positive integer n, n ≤ 50, representing
the number of states of a finite state machine with
input alphabet = output alphabet =50, 16 and an
n × 3 array representing the state table description of such a machine
Output: m × 3 array representing the state table
of a minimized version of M
11. Input: Set of terminals in a grammar and a description of the productions in a grammar; ability
for the user to set a maximum number of steps for
any derivation
Output: List of words in the language that can be
derived within that maximum
12. Write a finite-state machine simulator. That is,
given
• a positive integer n, n ≤ 50, representing the
number of states of a finite state machine with
input alphabet = output alphabet = 50, 16
• an n × 3 array representing the state table
description of such a machine
your program should request input strings and
write the corresponding output strings as long as
the user wishes.
13. Write a Turing machine simulator. That is, given
a set of quintuples describing a Turing machine,
your program should request the initial tape contents and write out a sequence of successive tape
configurations. Assume that there are at most 100
quintuples and that the number of cells used on
the tape is at most 70, and allow the user to set a
maximum number of steps in case the computation does not halt before then
Chapter 9 Review
801
For Exercises 1–11, write a computer program that
produces the desired output from the given input.
1. Input: Two words from an alphabet A
Output: Their concatenation
2. Input: Positive integer n and finite alphabet A
Output: All words over A of length ≤ n
3. Input: Positive integer n
Output: Tables for addition and multiplication
modulo n
4. Input: Positive integer n
Output: The n! elements of S n expressed both in
array form and in cycle notation, the group table for
3S n , + 4, and the group table for 3A n , + 4
5. Input: n × n array, n ≤ 10, that purports to represent a binary operation on the finite set of integers
from 1 to n
Output: Determination of whether the set under this
operation is a commutative group
6. Input: Two n × n arrays, n ≤ 10, that represent
two groups and an array that represents a function
from the first group to the second
Output: Determination of whether the function is
an isomorphism
7. Input: A canonical n × r parity-check matrix H
for a single-error correcting code with r ≤ 4 and
n ≤ 2
r
−1
Output: The set of binary m-tuples H encodes and
the code word for each one
8. Input: A canonical parity-check matrix for a perfect
single-error correcting code where r ≤ 5 and any
binary n-tuple X
Output: The binary n-tuple to which X is decoded
9. Input: Positive integer n, n ≤ 50, representing the
number of states of a finite-state machine with input alphabet = output alphabet = 50, 16 and an
n × 3 array representing the state table description
of such a machine
Output: List of any states unreachable from the
start state s 0
10. Input: Positive integer n, n ≤ 50, representing
the number of states of a finite state machine with
input alphabet = output alphabet =50, 16 and an
n × 3 array representing the state table description of such a machine
Output: m × 3 array representing the state table
of a minimized version of M
11. Input: Set of terminals in a grammar and a description of the productions in a grammar; ability
for the user to set a maximum number of steps for
any derivation
Output: List of words in the language that can be
derived within that maximum
12. Write a finite-state machine simulator. That is,
given
• a positive integer n, n ≤ 50, representing the
number of states of a finite state machine with
input alphabet = output alphabet = 50, 16
• an n × 3 array representing the state table
description of such a machine
your program should request input strings and
write the corresponding output strings as long as
the user wishes.
13. Write a Turing machine simulator. That is, given
a set of quintuples describing a Turing machine,
your program should request the initial tape contents and write out a sequence of successive tape
configurations. Assume that there are at most 100
quintuples and that the number of cells used on
the tape is at most 70, and allow the user to set a
maximum number of steps in case the computation does not halt before then
Chapter 9 Review
801