#Test Bank Languages and Machines An Introduction to the Theory 3rd Edition Solution | Explore Tumblr posts and blogs

Test Bank Languages and Machines An Introduction to the Theory 3rd Edition Solution

For Order This And Any Other Test

Banks And Solutions Manuals, Course,

Assignments, Discussions, Quizzes, Exams,

Chapter 1

Mathematical Preliminaries

5. To prove that X ∩ Y = (X ∪ Y) requires establishing both of the inclusions X ∩ Y ⊆ (X ∪ Y) and (X ∪ Y) ⊆ X ∩ Y.

i) Let a ∈ X ∩ Y. By the definition of intersection, a ∈ X and a ∈Y.Thus a ∈ X and a ∈ Y or, in terms of union, a ∈ (X ∪ Y). It follows that a ∈ (X ∪ Y).

ii) Now assume that a ∈ (X ∪ Y). Then a ∈ X ∪ Y. This implies that a ∈ X and a ∈ Y. Consequently, a ∈ X ∩ Y.

Part (i) shows that X ∩ Y is a subset of (X ∪ Y), while (ii) establishes the inclusion (X ∪ Y) ⊆ X ∩ Y.

A completely analogous argument can be used to establish the equality of the sets (X ∩ Y) and X ∪ Y.

6. a) The function f (n) = 2n is total and one-to-one. However, it is not onto since the range

is the set of even numbers.

b) The function {

0 if n = 0

f (n) =

n−1 otherwise

is total and onto. It is not one-to-one since f (0) = f (1) = 0.

c) The function 

 1 if n = 0

f (n) = 0 if n = 1



n otherwise

is total, one-to-one, and onto but not the identity.

d) The function f (n) =

{

n/2 if n is even

↑ otherwise

maps the even natural numbers onto the entire set of natural numbers. It is not a total function from N to N, since it is not defined for odd natural numbers.

13. To prove that ≡p is an equivalence relation, we must show that it is reflexive, symmetric, and transitive. This is shown using the same argument given in Example 1.3.1, which explicitly considers the case when p = 2.

i) Reflexivity: For every natural number n, n mod p = n mod p. 1

2 CHAPTER 1. MATHEMATICAL PRELIMINARIES

ii) Symmetry: If n mod p = m mod p, then m mod p = n mod p.

iii) Transitivity: If n mod p = m mod p and m mod p = k mod p, then n mod p = k mod p. The equivalence classes of ≡p are the sets consisting of natural numbers that are equal mod p: [0]≡p = {0, p, 2p, 3p, . . .}

[1]≡p = {1, p + 1, 2p + 1, 3p + 1, . . .} [2]≡p = {2, p + 2, 2p + 2, 3p + 2, . . .}

[p − 1]≡p = {p − 1, 2p − 1, 3p − 1, 4p − 1, . . .}.

15. i) Reflexivity: To demonstrate reflexivity, we must show that every ordered pair [m, n] is

related to itself. The requirement for [m, n] to be related to [m, n] by ≡ is m + n = n + m, which follows from the commutativity of addition.

ii) Symmetry: If [m, n] ≡ [j, k], then m + k = n + j. Again, by commutativity, j + n = k + m and [j, k] ≡ [m, n].

iii) Transitivity: [m, n] ≡ [j, k] and [j, k] ≡ [s, t] imply m + k = n + j and j + t = k + s.

Adding the second equality to the first, we obtain

m + k + j + t = n + j + k + s.

Subtracting j + k from each side yields m + t = n + s, showing that [m, n] ≡ [s, t] as desired.

18. The set of non-negative rational numbers is defined by

{n/m | n ∈ N, m ∈ N − {0}}

A rational number n/m can be represented by the ordered pair [n, m]. This representation defines a one-to-one correspondence between the rational numbers and the set N × (N − {0}). The latter set is known to be countable by Theorem 1.4.4.

22. Diagonalization is used to prove that there are an uncountable number of monotone increasing functions. Assume that the set of monotone increasing functions is countable. Then these functions can be listed in a sequence f0, f1, f2, . . . ,fn,......

Now we will show that there is at least one (in fact there are infinitely many) monotone increasing function that is not in the listing. Define a function f as follows:

f (0) = f0(0) + 1

f (i) = fi(i) + f (i − 1)

for i > 0. Since fi(i) > 0, it follows that f (i) > f (i − 1) for all i and f is monotone increasing.

Clearly f (i) = fi(i) for any i, contradicting the assumption that f0, f1, . . ., fn, . . . exhaus- tively enumerates the monotone increasing functions. Thus the assumption that the monotone increasing functions comprise a countable set leads to a contradiction and we conclude that the set is uncountable.

25. To show that the set of real numbers in the interval [0, a] is uncountable, we first observe that

every real number in (0, 1] can be expressed by an infinite decimal .x0x1x2. . .xn.... With such

a representation, the number12 isrepresentedbyboth.50000...and.49999.............. To obtain a

SOLUTIONS TO EXERCISES 3

unique representation, we consider only decimal expansions that do not end with an infinite sequence of zeros.

Assume the set of real numbers in (0, 1] is countable. This implies that there is a sequence r0, r1, r2, ... ,rn, ...

that contains all of the real numbers in the interval (0, 1]. Let the decimal expansion of rn

be denoted .xn0xn1xn2........... The enumeration given above is used to construct an infinite

two-dimensional array, the ith row of which consists of the expansion of ri.

r0= x00 x01 x02

r1= x10 x11 x12

r2= x20 x21 x22

With the unique decimal representation, two numbers are distinct if they differ at any position in the decimal expansion. A real number r = x0x1 . . . is defined using the diagonal elements in the array formed by the xii’s as follows:

{

xi =

2 if xii = 1

1 otherwise.

Clearly r = ri for any i since the ith position of r, xi, is not identical to the ith position of ri. Therefore the assumption that the enumeration contains all real numbers in (0, 1] fails, and we conclude that the set is uncountable.

28. Before proving the Schröder-Bernstein Theorem, we consider the special case where card(B) ≤ card(A), card(A) ≤ card(B), and B ⊆ A.

The relationship card(B) ≤ card(A) follows immediately from the inclusion B ⊆ A since the identity function id : B → A is a one-to-one function from B into A.

By definition, card(A) ≤ card(B) means there is a one-to-one function f from A into B. We will use f to construct a one-to-one function h : A → B from A onto B. The function h demonstrates that A and B have the same cardinality.

The diagram

f A

B

4 CHAPTER 1. MATHEMATICAL PRELIMINARIES

illustrates the mapping f . The function f is defined for all elements in A (which includes all elements of B) and the values of f , indicated by the heads of the arrows, must all be in B.

For each x ∈ A − B, we define the set

ch(x) = {x, f (x), f (f (x))), . . . , fi(x), . . .}.

Every element in ch(x) is in B, except for x itself which is in A −B. Let ⋃

C= ch(x).

x∈ A−B

Now define the function h : A → B as follows:

{

f (z), if z ∈ C;

h(z) =

z, otherwise.

To show that h is a one-to-one, we must prove that h(x) = h(y) implies that x = y. There are four cases to consider.

Case 1: x, y ∈ C. Then x = h(x) = h(y) = y.

Case 2: x ∈ C and y ∈ C. Since x ∈ C, h(x) = f (x) is in C. But h(x) = h(y) = y. This implies that y ∈ C, which is a contradiction. Thus h(x) cannot equal h(y) in this case.

Case 3: x ∈ C and y ∈ C. Same argument as case 2.

Case 4: x, y ∈ C. Let fi denote the composition of f with itself i times, and f0 denote the identity function. The proof uses the fact that the composition of one-to-one functions is one- to-one. Although you will be familiar with functional composition from previous mathematical studies, a description and formal definition are given in Section 9.4 of the text if you need a reminder.

Since x and y are both in C, x = fm(s) and y = fn(t) for some s, t ∈ A − B. Then h(x) = f (fm(s)) = h(y) = f (fn(t)).

If m = n, then s = t and x = y and we are done. Assume that m > n. Then fm−n(s) = t. Applying the function fn to both sides we get fm(s) = fn(t), or equivalently, x = y. A similar argument shows x = y when m < n.

We now show that h maps A onto B. For each x ∈ B but not in C, h(x) = x and x is covered by the mapping. If x ∈ B and x ∈ C, then x = f (t) for some t ∈ C because each element in C is either in A − B or obtained by the result of applying f to an element in C. Consequently, each element of B is ‘hit’ by the mapping h. Because h is a one-to-one function from A to B, we conclude that card(A) = card(B).

To prove the Schröder-Bernstein Theorem in its generality, we must show that card(X) ≤card(Y) and card(Y) ≤ card(X) implies card(X) = card(Y) for arbitrary sets X and Y. By the assumption, there are one-to-one functions f : X → Y and g : Y → X. Let

Im(Y) = {x ∈ X | x = g(y) for some y in Y}

be the image of Y in X under g. Now

- Im(Y) is a subset of X,

- Im(Y) has the same cardinality as Y (g is one-to-one and onto), and

- the composition f ◦ g is a one-to-one mapping from X into Im(Y).

SOLUTIONS TO EXERCISES 5

By the preceding result, card(X) = card(Im(Y)). It follows that card(X) = card(Y) by Exercise 27.

31. Let L be the set of the points in N × N on the line defined by n = 3 · m. L can be defined recursively by

Basis: [0, 0] ∈ L.

Recursive step: If [m, n] ∈ L, then [s(m), s(s(s(n)))] ∈ L.

Closure: [m, n] ∈ L only if it can be obtained from [0, 0] using finitely many applications of the recursive step.

33. The product of two natural numbers can be defined recursively using addition and the successor operator s.

Basis: if n = 0 then m · n = 0

Recursive step: m · s(n) = m + (m · n)

Closure: m · n = k only if this equality can be obtained from m · 0 = 0 using finitely many applications of the recursive step.

37. The set F of finite subsets of the natural numbers can be defined recursively as follows: Basis: ∅, {0} ∈ F

Recursive step: If {n} ∈F , then {s(n)} ∈ F . If X, Y ∈F , then X ∪ Y ∈ F .

Closure: A set X is in F only if it can be obtained from the basis elements by a finite number of applications of the recursive step.

The first rule in the recursive step generates all sets containing a single natural number. The second rule combines previously generated sets to obtain sets of larger cardinality.

39. We prove, by induction on n, that

∑

2i = 2n+1−1

i=0

Basis: The basis is n = 0. We explicitly show that the equality holds for this case. ∑

2i = 20 = 1 = 21−1

i=0

Inductive hypothesis: Assume, for all values k = 1, 2, . . . , n, that ∑

2i = 2k+1− 1

i=0

Inductive step: We need to show that

∑

2i = 2(n+1)+1−1

i=0

To utilize the inductive hypothesis, the summation is decomposed into the sum of the first n powers of 2 and 2n+1.

n

0k

n+1

6 CHAPTER 1. MATHEMATICAL PRELIMINARIES

∑ n∑

2i = 2i + 2n+1

i=0 i=0

= 2n+1−1+2n+1 (inductive hypothesis)

= 2·2n+1−1 = 2(n+1)+1−1

43. The set R of nodes reachable from a given node x in a directed graph is defined recursively using the adjacency relation A.

Basis: x ∈ R.

Recursive step: If y ∈ R and [y, z] ∈ A, then z ∈ R.

Closure: y ∈ R only if y can be obtained from x by finitely many applications of the recursive step.

46. a) The depth of the tree is 4.

b) The set of ancestors of x11 is {x11, x7, x2, x1}. Recall that by our definition is node is an ancestor of itself, which is certainly not the case in family trees.

c) The minimal common ancestor of x14 and x11 is x2; of x15 and x11 is x1.

d) The subtree generated by x2 is comprised of the arcs [x2, x5], [x2, x6], [x2, x7], [x5, x10], [x7, x11], and [x10, x14].

e) The frontier is the set {x14, x6, x11, x3, x8, x12, x15, x16}.

48. Induction on the depth of the tree is used to prove that a complete binary tree T of depth n has 2n+1− 1 nodes. Let nodes(T) and leaves(T) denote the number of nodes and leaves in a tree T.

Basis: The basis consists of trees of depth zero; that is, trees consisting solely of the root. For any such tree T, nodes(T) = 1 = 21− 1.

Inductive hypothesis: Assume that every complete binary tree T of depth k, k = 0, . . . , n, satisfies nodes(T) = 2k+1− 1.

Inductive step: Let T be a complete binary tree of depth n + 1, where n ≥ 0. We need to show that nodes(T) = 2(n+1)+1− 1. T is obtained by adding two children to each leaf of a complete binary tree T′ of depth n. Since T′ is complete binary, it is also strictly binary and

leaves(T′) = (nodes(T′) + 1)/2

by Exercise 47. Thus

nodes(T) = nodes(T′) + 2 · leaves(T′)

= nodes(T′) + 2 · [(nodes(T′) + 1)/2] (Exercise 47) = 2 · nodes(T′) + 1

= 2 · (2n+1− 1) + 1 (inductive hypothesis)

=2(n+1)+1−1

n+1