| Homework Assignments | |
| Please use the <Discussion Board> to ask questions about the homework. Click on <Communication>, then <Discussion Board> ()()Sets of problems in parentheses count as a single, five-point problem.()() |
|
| Problem set 1 Due January 31 |
(1.24 and 1.26) (1.27 and 1.28) (1.36 and 1.38) |
| Problem set 2 Due February 21 |
1. Let M be a deterministic PDA with a stack
whose size is limited to 3 elements. Give a context-free language
which M cannot recognize, and prove that M cannot recognize it. 2. Build PDAs (you may use nondeterminism) to recognize each of the following languages: L1 = {aibjck | i >= j} L2 = {aibjck | j >= k} L3 = {aibjck | k >= i} Use the three languages above and an example from the book to show that the intersection of two context-free languages is not necessarily context-free. 3. Use the pumping lemma for context-free languages to show that P = {ap | p is a prime number} is not a context-free language. (Hint: The book does this for regular languages.) 4. 2.17 from the book. Please do not consult outside sources, such as the Internet. |
| Problem set 3 Due February 28 |
1. Describe a Turing machine
which never halts on the empty input, and whose state sequence never
becomes periodic. (Note: The state sequence is the sequence of
states the associated DFA enters during this infinite
computation. And a sequence q1q2q3q4q5q6q7... is called periodic if it is of the form
ABBB... where A and B are each finite sequences of states, and the Bs
repeat forever. For example, the following sequence is
periodic: 31415926592659265926592659265...) 2. A DFAQ is a DFA endowed with an unbounded queue. Items are popped from the front of the queue and pushed to the end of the queue, and the transition function is no longer d:Q×Sigma-->Q, but d:Q×Gamma-->Q×Gamma, where Gamma is the queue alphabet (which includes Sigma), the second coordinate in the domain is the symbol popped from the queue, and the second coordinate in the codomain is the item that is pushed onto the queue. Note that that epsilon may be read from or pushed to the queue, and that this does not wreck the deterministic nature of the DFAQ. Also note that our DFAQ does not read an input string: The "input" must be placed on the queue prior to the start of computation. Prove that a DFAQ is equivalent to a Turing machine. 3. A key idea in the proof that a language is Turing-decideable if and only if it is decideable by a nondeterministic Turing machine was the fact that any tree with a) every vertex of finite degree and b) every path from the root to a leaf has finite length, must have a finite number of vertices. a. Prove this fact b. Give an example that shows that finite degree alone will not guarantee a finite number of nodes in the graph c. Give an example that shows that finite branch length alone will not guarantee a finite number of nodes in the graph. 4. Let's explore the relationship between context-free languages and Turing machines: a. Prove that every context-free language is Turing decideable. b. Let L = {<P, w> | P is a pushdown automaton which accepts the string w}. Prove that L is Turing-decideable. 5. Prove that the complement of a Turing-decideable language is Turing-decideable. Must the complement of a Turing-recognizable language be Turing-decideable? Must it be Turing-recognizable? 6. The Collatz Problem: Give a mid-level description of a Turing machine which determines whether an input binary number terminates under the Collatz iteration, whether it enters a loop or whether it runs forever without repeating a value. By "determines," do we mean in the "recognizing" or "deciding" sense? Here's the Collatz iteration: If a number is even, divide it by 2. If a number is odd, triple it and add 1. If you reach "1," terminate. For example, starting with 7: 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (terminate). |
| Problem Set 4 Due March 28 |
1. For a string w, let L*(w) = {<M> | M is a T.M. which
accepts w}. For which w is L*(w) Turing-Recognizable? For
which w is L*(w) Turing-Decidable? 2. Let EQstring = {<v, w> | L*(v) = L*(w)}, using the terminology of the previous problem. Prove that EQstring is Turing decidable. 3. We have seen languages which are not Turing-recognizable, but these languages tended to be very specific encodings of machines. a. Prove that there is a language over the alphabet {a} which is not Turing-recognizable b. Build a language as follows: List all the strings over {0, 1}, and then go down that list, flipping a coin for each string and including it in the language if and only if you get Heads. What is the probability that the resulting language will be Turing-recognizable? 4. Let A17 = {<M> | L(M) contains at least 17 strings}. Prove that A17 is Turing-recognizable but not Turing-decidable. |
| Problem Set 5 |
(Please do not
consult the Internet for these problems.) 1. S and T are alphabets, and Alice and Bob are translators.  Given a string w
over S, Alice (or Bob) goes symbol-by-symbol through w looking up each symbol in thier
translation dictionary for the string over T corresponding to that
symbol, and concatenating the translations to form the string (over T)
which is the translation of w.
In the example to the right, S = {a, b, c, d, e, f, g, h} and T = {0,
1}, and if w = "gab," then
the translation f (w) = "000001001001." On the day of the Great Demonstration, Alice and Bob are to show The Boss how quickly they can translate. The Boss will select a string w, and then Alice and Bob go to separate rooms, with their dictionaries, perform the translation and then The Boss compares the translations to make sure they are identical. Unfortunately, Alice and Bob brought different dictionaries to the Great Demonstration. In other words, Alice has a function f and Bob has a function g. When they realize this, they quickly try to find a string w* such that f (w*) = g(w*), in the hopes that they could convince The Boss to allow them to translate that string. Show that the problem of finding such a w* given the functions f and g is undecidable. 2. A "useless state" in a TM is one that is never visited under any input. Let U = {<M> | M is a TM with a useless state}. Use mapping reduction to show that U is not Turing-Decidable. Use mapping reduction to show that U is not Turing-Recognizable. 3. Show that U is co-Turing-Recognizable. 4. Given a positive integer n, let L(n) be the length of the longest string that a Turing machine with n states can print out over the alphabet {0, 1}, and then halt, when starting with a blank tape. a. Show that L(n) is well-defined. That is, show that L(n) exists and is finite for every positive integer n. b. Show that L(n) is not computable. |
| Problem set 6 |
1: A language L is said to be in
P-SPACE if there exists a polynomial p(n) and a TM which
can decide it using a tape of size p(n), where n
is, as usual, the size of the input. Show that L in P
implies L in P-SPACE. 2: A language is said to be in co-NP if it's complement is in NP. a. Prove that P is a subset of co-NP b. Show that if co-NP contains an NP-complete problem, then NP = co-NP. c. We mentioned in class that PRIMES is in P. Use this fact to show that FACTOR is in both NP and co-NP. (The FACTOR problem has as input some positive integers n and b, and the problem is to decide if n has a factor less than b, aside from '1'.) 3: a. Use the fact that 3-COLORABLE is NP-Complete to prove that 3-CLUSTERING is NP-Complete. b. Prove that 2-COLORING is in P. Extra credit: Prove that 3-COLORABLE is NP-Complete. 4: Some theory questions a. Does NP contain any undecidable languages? b. How about co-NP? c. Suppose language L can be decided in time n^4, and language M can be reduced to language L in time n^5. Furthermore, language N can be reduced to language M in time n^3. We therefore have a polynomial decider for language N which runs in polynomial time and ultimately uses the decision algorithm for language L. What is the running time for this decider for language N? |