UMBC CMSC651, Automata Theory & Formal Languages, Fall 2010

Homework Assignments

Homework 1, Due Thursday, 09/09

1. Problem 3.14, page 161.

2. Problem 3.16, parts b, c & d, page 161.

3. Problem 3.19, page 162.
   Hint: you may assume that Problem 3.18 has been solved.

Homework 2, Due Thursday, 09/16

1. Show that the version of the Halting Problem defined below is undecidable.

   K = { i  |  M_i is a TM that halts on blank input }.

   Note: do not use Rice's Theorem.

2. Problem 5.16, page 212.

3. Show that E_TM many-one reduces to FINITE, where

   E_TM = { ⟨ M ⟩  |  M is a TM such that L(M) = ∅ }

   and

   FINITE = { ⟨ M ⟩  |  M is a TM such that L(M) is a finite set }.

Homework 3, Due Thursday, 09/23

1. Problem 4.19 4.18, page 184.
   Note: Carefully argue that a) the language of the machine M you constructed is actually separates A from B, and that b) M always halts even if other machines that M is simulating could run forever.

2. Express the following languages using first-order quantifiers (∃ and ∀ over natural numbers or strings) followed by a decidable predicate:

   COFINITE = { ⟨ M ⟩ | the complement of L(M) is finite }

   SUBSET = { ⟨ M₁, M₂ ⟩ | L(M₁) ⊆ L(M₂) }

   Use as few quantifiers as you can and place all of the quantifiers at the beginning. In particular, none of the quantifiers should appear after a negation.

3. Let £₁, £₂, £₃, ... be a list of linearly bounded automata (LBA) as defined in Section 5.1 of the textbook. We can encode LBAs in the same manner that TMs are encoded. We say that £_i is minimal if for all j such that L(£_i) = L(£_j), ⟨ £_i ⟩ < ⟨ £_j ⟩. That is, £_i is minimal if it has the lexicographically smallest encoding of all the LBAs that recognize the same language.

   Let

   MIN_LBA = { ⟨ £_i ⟩ | £_i is minimal }.

   Show that MIN_LBA is Turing recognizable.

Homework 4, Due Thursday, 09/30

1. Let MIN_LBA be as defined in Homework 3. Show that MIN_LBA is undecidable.

2. Show that INFINITE many-one reduces to ALL_TM where

   INFINITE = { ⟨ M ⟩  |  M is a TM and L(M) is an infinite set }

   and

   ALL_TM = { ⟨ M ⟩  |  M is a TM and L(M) = Σ* }.

   Note: You must construct a computable function f such that for all TM's M

   ⟨M⟩ ∈ INFINITE if and only if f (⟨M⟩) ∈ ALL_TM.

   Carefully argue that the f  you constructed is indeed computable and that both directions of the "if and only if" hold.

3. Problem 6.22, page 243.

Homework 5, Due Thursday, 10/14

1. Show that the function f (n) = n log₂ n is space constructible. (See Definition 9.1 for the definition of "space constructible".)

2. Show that SPACE[ n⁵ ] is immune to SPACE[ n³ ]. That is, show that there is an infinite set A ∈ SPACE[ n⁵ ] such that for all B ⊆ A, where B ∈ SPACE[ n³ ], the set B must be finite.

3. Prove that any Turing recognizable set A can be written as

   A = C / D = { x ∈ Σ^* | w = xy for some w ∈ C and y ∈ D }

   for some C and D in SPACE[ log n ].

Homework 6, Due Thursday, 10/21

1. Problem 9.13, page 362.

2. Show that P ≠ SPACE[ n³ ].
   Hint: think about pad( A, n² ) for some A ∈ SPACE[ n⁶ ].

Homework 7, Due Thursday, 10/28

1. Show that the log-space transducers defined on page 324 of Sipser is transitive. I.e., show that if A ≤_L B and B ≤_L C then A ≤_L C.

2. The description of the PATH problem in Section 7.2 uses adjacency matrices to represent graphs on the input tape of a Turing machine. Show that a log-space transducer can convert a graph given as a list of edges into its adjacency matrix representation. Here, assume that '(', ',' and ')' are part of the input alphabet. Also, consider carefully how your transducer handles the case of large sparse matrices, where the input might look like

   (1,2), (2,8713470183741023847120).

   where the length of 8713470183741023847120 might be much larger than log n. (It might be √n, for example.)

   You may ignore isolated vertices (vertices without any edges attached). So, in the example above, you can generate an adjacency matrix for the graph

   (1,2), (2,3).

   I.e., if the vertices numbered between 2 and 8713470183741023847120 do not appear on the adjacency list, you can assume that they don't exist. However, you still have to deal with the fact that 8713470183741023847120 is a rather large number and might have length bigger than log n.

3. Argue that the Immerman-Szelepcsenyi Theorem extends to nonconstructible space bounds above log n. I.e., show that for all space bounds s(n) ≥ log n, NSPACE [ s(n) ] = coNSPACE [ s(n) ].

4. Extra Credit: Problem 8.23, page 331.
   Note: since the graph G might not be connected, it does not suffice to simply count the number of edges. If the undirected graph G does not have any cycles, then it is simply a collection of trees.

Homework 8, Due Thursday, 11/04

1. Problem 7.23, page 296.

2. Problem 7.36, page 298.

3. Problem 7.39, page 299.

4. Extra Credit: Problem 7.28, page 297.

Homework 9, Due Thursday, 11/18

1. Problem 10.12, page 412.

2. The definition of circuit family is given on page 354 (Definition 9.27). We say that a language L has polynomial-sized circuits if L is decided by a circuit family C = ( C₀, C₁, C₂, ... ) where the size of C_n is bounded by a polynomial in n.

   Show that if a language L has polynomial-sized circuits, then there exists a sparse set S such that L ∈ P ^S.

   Hint: you can stuff the circuit C_n in the sparse set S, but how do you get it out?

3. Show that if there exists a sparse set S such that coNP ⊆ NP ^S, then PH collapses to Σ^P₃.

   Hint: mimic Karp-Lipton-Sipser, but be careful how you check if the sparse set you guessed "works".

Homework 10, Due Thursday, 12/02

1. Problem 10.11, page 412.

2. We say that a language L is in the class PP if there exists a deterministic polynomial-time Turing machine M and a polynomial p() such that

   x ∈ L ⇒ Prob _r [ M(x, r) accepts ] > ½

   x ∉ L ⇒ Prob _r [ M(x, r) accepts ] < ½

   where the probability is taken over r ∈ {0,1}^p(n) and n = | x | .

   Show that NP ⊆ PP.

3. Let N be a nondeterministic Turing machine. We define the function #acc_N(x) to be number of accepting paths in the computation of N on input x.

   We say that a function f  is in the class #P if there exists a nondeterministic polynomial-time Turing machine N such that for all x ∈ Σ^*,  f (x) = #acc_N(x).

   Show that the class #P is closed under addition and multiplication. That is, for any two functions f and g in #P, the functions

   h₁(x) = f (x) + g(x)

   and

   h₂(x) = f (x) ⋅ g(x)

   must also be in #P.

Homework 11, Due Thursday, 12/09