100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
Exam (elaborations) TEST BANK FOR Introduction to the Theory of Computation 3rd Edition By Michael Sipser (Solution Manual) $15.49   Add to cart

Exam (elaborations)

Exam (elaborations) TEST BANK FOR Introduction to the Theory of Computation 3rd Edition By Michael Sipser (Solution Manual)

 237 views  1 purchase

Exam (elaborations) TEST BANK FOR Introduction to the Theory of Computation 3rd Edition By M. (Michael) Sipser (Solution Manual) Instructor’s Solutions Manual for Introduction to the Theory of Computation third edition Michael Sipser Mathematics Department MIT c 2013 Cengage Learning. A...

[Show more]

Preview 4 out of 90  pages

  • November 15, 2021
  • 90
  • 2021/2022
  • Exam (elaborations)
  • Questions & answers
book image

Book Title:

Author(s):

  • Edition:
  • ISBN:
  • Edition:
All documents for this subject (1)
avatar-seller
Expert001
, Instructor’s Solutions Manual for
Introduction to the Theory of Computation
third edition



Michael Sipser
Mathematics Department
MIT




c 2013 Cengage Learning. All Rights Reserved. This edition is intended for use outside of the U.S. only, with content that may be
different from the U.S. Edition. May not be scanned, copied, duplicated, or posted to a publicly accessible website, in whole or in part.

, Chapter 0


0.1 a. The odd positive integers.
b. The even integers.
c. The even positive integers.
d. The positive integers which are a multiple of 6.
e. The palindromes over {0,1}.
f. The empty set.

0.2 a. {1, 10, 100}.
b. {n| n > 5}.
c. {1, 2, 3, 4}.
d. {aba}.
e. {ε}.
f. ∅.

0.3 a. No.
b. Yes.
c. A.
d. B.
e. {(x, x), (x, y), (y, x), (y, y), (z, x), (z, y)}.
f. {∅, {x}, {y}, {x, y}}.

0.4 A × B has ab elements, because each element of A is paired with each element of B, so
A × B contains b elements for each of the a elements of A.

0.5 P(C) contains 2c elements because each element of C may either be in P(C) or not in
P(C), and so each element of C doubles the number of subsets of C. Alternatively, we
can view each subset S of C as corresponding to a binary string b of length c, where S
contains the ith element of C iff the ith place of b is 1. There are 2c strings of length c
and hence that many subsets of C.

0.6 a. f (2) = 7.
b. The range = {6, 7} and the domain = {1, 2, 3, 4, 5}.
c. g(2, 10) = 6.
d. The range = {1, 2, 3, 4, 5} × {6, 7, 8, 9, 10} and the domain = {6, 7, 8, 9, 10}.
e. f (4) = 7 so g(4, f (4)) = g(4, 7) = 8.


1
c 2013 Cengage Learning. All Rights Reserved. This edition is intended for use outside of the U.S. only, with content that may be
different from the U.S. Edition. May not be scanned, copied, duplicated, or posted to a publicly accessible website, in whole or in part.

, 2 Theory of Computation, third edition

0.7 The underlying set is N in these examples.
a. Let R be the “within 1” relation, that is, R = {(a, b)| |a − b| ≤ 1}.
b. Let R be the “less than or equal to” relation, that is, R = {(a, b)| a ≤ b}.
c. Finding a R that is symmetric and transitive but not reflexive is tricky because of the
following “near proof” that R cannot exist! Assume that R is symmetric and transitive
and chose any member x in the underlying set. Pick any other member y in the underlying
set for which (x, y) ∈ R. Then (y, x) ∈ R because R is symmetric and so (x, x) ∈ R
because R is transitive, hence R is reflexive. This argument fails to be an actual proof
because y may fail to exist for x.
Let R be the “neither side is 1” relation, R = {(a, b)| a = 1 and b = 1}.

0.10 Let G be any graph with n nodes where n ≥ 2. The degree of every node in G is one
of the n possible values from 0 to n − 1. We would like to use the pigeon hole principle
to show that two of these values must be the same, but number of possible values is too
great. However, not all of the values can occur in the same graph because a node of
degree 0 cannot coexist with a node of degree n − 1. Hence G can exhibit at most n − 1
degree values among its n nodes, so two of the values must be the same.

0.11 The error occurs in the last sentence. If H contains at least 3 horses, H1 and H2 contain
a horse in common, so the argument works properly. But, if H contains exactly 2 horses,
then H1 and H2 each have exactly 1 horse, but do not have a horse in common. Hence
we cannot conclude that the horse in H1 has the same color as the horse in H2 . So the 2
horses in H may not be colored the same.

0.12 a. Basis: Let n = 0. Then, S(n) = 0 by definition. Furthermore, 12 n(n + 1) = 0. So
S(n) = 12 n(n + 1) when n = 0.
Induction: Assume true for n = k where k ≥ 0 and prove true for n = k + 1. We
can use this series of equalities:

S(k + 1) = 1 + 2 + · · · + k + (k + 1) by definition
= S(k) + (k + 1) because S(k) = 1 + 2 + · · · + k
= 12 k(k + 1) + (k + 1) by the induction hypothesis
= 12 (k + 1)(k + 2) by algebra

b. Basis: Let n = 0. Then, C(n) = 0 by definition, and 14 (n4 + 2n3 + n2 ) = 0. So
C(n) = 14 (n4 + 2n3 + n2 ) when n = 0.
Induction: Assume true for n = k where k ≥ 0 and prove true for n = k + 1. We
can use this series of equalities:

C(k + 1) = 13 + 23 + · · · + k 3 + (k + 1)3 by definition
= C(k) + (k + 1) 3
C(k) = 13 + · · · + k 3
= 14 (n4 + 2n3 + n2 ) + (k + 1)3 induction hypothesis
1 4 3 2
= 4 ((n + 1) + 2(n + 1) + (n + 1) ) by algebra

0.13 Dividing by (a − b) is illegal, because a = b hence a − b = 0 and division by 0 is
undefined.




c 2013 Cengage Learning. All Rights Reserved. This edition is intended for use outside of the U.S. only, with content that may be
different from the U.S. Edition. May not be scanned, copied, duplicated, or posted to a publicly accessible website, in whole or in part.

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller Expert001. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for $15.49. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

71184 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling
$15.49  1x  sold
  • (0)
  Add to cart