Introduction to the Theory of Computation 3rd. Edition by Michael Sipser | 9781133187790 | 113318779X | Holooly

Introduction to the Theory of Computation

72 SOLVED PROBLEMS

Question: 1.7

Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0,1}. a. The language {w| w ends with 00} with three states f. The language 1^* (011^+)^* with three states ...

Verified Answer:

Question: 10.16

Prove that for any integer p > 1, if p isn’t pseudoprime, then p fails the Fermat test for at least half of all numbers in Zp^+ . ...

Verified Answer:

Call a a witness if it fails the Fermat test for p...

Question: 10.7

Show that BPP ⊆ PSPACE. ...

Verified Answer:

If M is a probabilistic TM that runs in polynomial...

Question: 9.15

Define pad as in Problem 9.13. a. Prove that for every A and natural number k, A ∈ P iff pad(A, n^k) ∈ P. b. Prove that P ≠ SPACE(n). ...

Verified Answer:

(a) Let A be any language and k ∈ N. If A ∈ P, the...

Question: 9.7

Give regular expressions with exponentiation that generate the following languages over the alphabet {0,1}. a. All strings of length 500 b. All strings of length 500 or less c. All strings of length 500 or more d. All strings of length different than 500 ...

Verified Answer:

(a)

\Sigma ^{500}

; (b)

(\Sig...

Question: 9.3

Prove that NTIME(n) ⊊ PSPACE. ...

Verified Answer:

NTIME(n)\subseteq NSPACE(n)

because...

Question: 9.2

Prove that TIME(2^n) ⊊ ( TIME(2^2n). ...

Verified Answer:

The containment

TIME (2^{n}) ⊆ TIME (2^{2n+...

Question: 6.3

Show that if A ≤T B and B ≤T C, then A ≤T C. ...

Verified Answer:

Say that

M^{B}_{1}

decides A and [l...

Question: 5.30

Use Rice’s theorem, which appears in Problem 5.28, to prove the undecidability of each of the following languages. a. INFINITETM = {〈M〉 | M is a TM and L(M) is an infinite language}. ...

Verified Answer:

(a)

INFINITE_{TM}

is a language of ...

Question: 5.28

Rice’s theorem. Let P be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine’s language has property P is undecidable. In more formal terms, let P be a language consisting of Turing machine descriptions where P fulfills ...

Verified Answer:

Assume for the sake of contradiction that P is a d...

Loading...