All Homework

Homework 1

1. Write a formal description for each of the following sets
   1. The set containing all integers which are multiples of 3 and are larger than 17.
   2. The set containing all integers which have either 2 or 3 (or both) as a factor.
2. Let A = {1,2,3,4}, and B = {X,Y,Z}.
   1. List the elements of A×B
   2. List the elements of B×A
   3. What is |P(A×B)|?
3. Use induction to prove that 2⁰ + 2¹ + 2² + ... + 2^k = 2^k+1-1 for k > 0.
4. Prove that congruence modulo n is an equivalence relation on the set of integers. Use the following definition of congruence in your proof: a≡b mod n if and only if a-b=kn for some integer k.

Homework 2

Notice that all of the problems ask for state diagrams, not state tables.

1. 1.3
2. 1.4c (Show all three diagrams)
3. 1.5c (Show both diagrams)
4. 1.5g (Show both diagrams)
5. 1.6a
6. 1.6c
7. 1.6g

Homework 3

1. 1.7e
2. 1.7g
3. 1.8b
4. 1.9b
5. 1.10b
6. 1.16b (Show the intermediate automata)
7. 1.32

Further details

• For several of the problems, remember that the empty set and the empty string are not the same thing.
• For 1.8b, 1.9b, and 1.10b, you may use NFAs for the initial languages. Please provide the NFAs/DFAs for the initial language(s) and then show the combined one unsimplified. Then simplify if you wish.
• For 1.32 providing a DFA/NFA is a proof (see results in the chapter that imply this). I prefer a state diagram for this problem since it is usually much easier to follow than a formal definition or table.

Homework 4

Problem	Comments
1.12	Notice that it is asking for a DFA (not an NFA) and a regular expression. Also notice that the DFA has to have 5 states.
1.18b	Create one based on the descriptions, not based on an NFA/DFA. Trust me, it is much harder to do the conversion from an NFA/DFA.
1.18c	See previous comment.
1.18e	See previous comment.
1.19b	Read the problem! Use the procedure and don't remove states that seem unnecessary. The point is to demonstrate the procedure.
1.20c
1.20e
1.20h
1.39	It is not enough to provide an example language for each value of k that seems to require at least k states. You need to be certain that it is impossible to do with k-1.

Homework 5

1. 1.21b. First rip out 1, then 2, and then 3. Make sure you show intermediate steps of the procedure!
2. 1.29b
3. 1.30
4. 1.32 (Use a DFA)
5. 1.49a (Clarification: k can be any value. It is not a fixed value. In other words, if you can find some value k such that you can write it in this form, then a string is in the language. Hint: Describe the language more simply.)
6. 1.49b
7. 1.55g
8. 1.62

Homework 6

Problem	Comments	Points
2.1	Don't forget to give BOTH the parse tree and derivation.	12
2.4b	Your grammar should be as simple as possible.	5
2.4c	Your grammar should be as simple as possible.	5
2.4e	Your grammar should be as simple as possible.	5
2.5a		5

Homework 7

Problem	Comments
2.2a	First, you have to prove whether or not A and B are CFL. Then use that result together with Exercise 2.36 to prove the result.
2.5e	Make sure your informal description is very clear and includes all pertinent details.
2.6b
2.12	Make sure to show any necessary work.
2.15	Don't make this harder than it is.
2.16	Make sure you do all three parts. Also, think about grammars and not PDAs.

Homework 8

Problem	Comments
2.13	Notice that part(b) ask to prove it is not regular. This tripped me up for a few minutes.
2.26	This is not too difficult, but your proof needs to be worded very clearly.
2.31	Make sure you take into account all possibilities. Also make sure you are very clear in your wording.
2.32	See comment on previous problem.

Homework 9

Problem	Points	Hints
3.8b	5	Read the solution to part a. Your answer should be in the same form.
3.8c	5	This one is easy if you simply make the appropriate modifications to your solution to part b. In fact, you can phrase your answer by describing how to modify your answer to part b. Alternatively, you can use your TM from part b in your TM for this problem.
3.12	5	Show how to simulate a regular TM with a Turing machine with left reset. Be very precise in your description and carefully read your answer to ensure that it contains all of the necessary details.
3.15b	5	Read the solution to part a. Your solution should be similar in that you need to describe a TM based on one or two other TMs. Make sure you include all of the details that the given solution contains to ensure full credit.
3.15d	5	See comment for previous problem.
Problem in Hint-->	5	Explain why your construction for 3.15d does not work for Turing-recognizable languages.

General Hints: Remember that a TM is not guaranteed to halt unless it is a decider and that a decider always needs to halt.

Homework 10

Problem	Points	Comments
4.2	5	Make sure to do both parts! This problem is pretty easy. If you are having a difficult time with it, you probably need to re-read the chapter and pay closer attention to the examples.
4.4	5	Don't make this one harder than it is.
4.6	6	This one should be pretty easy.
4.8	4	(Bonus! You can skip this one if you would like.) To prove a set is countable, you can define a one-to-one function from elements of the set to the natural numbers. Notice I did not say that it has to be onto. (This is because if you can define a one-to-one mapping from a set to a subset of the natural numbers, clearly the set is no larger than the size of the natural numbers, so it must be countable.) There are many very straightforward functions that can work, but seeing what to do can be tricky.
4.16	5	Regular languages are closed under intersection. Use this and a TM from the chapter to show that A is decidable.
4.24	5	(Bonus! You can skip this one if you would like.) Make sure to do both parts!
Problem 1 below	5	Read the problem below! Assume it is decidable and use a TM that decides this to construct a TM to decide a language you know is undecidable—like one discussed in section 5.1.

Problem 1

Let VERIFY_TM = { ⟨M,D⟩ | M is a TM which does D}. For instance, D might be "sorts a given list", or "finds the maximum clique in a given graph." Prove that VERIFY_TM is undecidable.

• If a problem asks to prove a language is decidable, you need to provide a high-level description of a TM that decides the language.
• The solutions to 4.10, 4.12, and/or 4.14 might help you think about how to do several of these problems.
• Use the theorems in the chapter. For instance (this is a random example which may or may not apply to any of the problems), Theorem 4.4 tells you that E_DFA is decidable. Exercise 4.10 uses this fact to construct a TM to decide the given language.

Homework 11

1. 7.1
2. 7.2
3. 7.3
4. If f(x) = O(g(x)), is it always the case that f(x) = o(g(x))? Explain, giving an example if appropriate. (Hint: an example is probably appropriate.)
5. Is TIME(log₂ (n)) = TIME(log₃(n))? In other words, do the functions log₂(n) and log₃(n) grow at the same rate? Explain and give the page number(s) in the textbook where you got the information.
6. If I have an algorithm that takes time n log (n) on a 7-tape Turing machine, how long will it take on a single-tape Turing machine. Make sure to express your answer properly. (Hint: Big-O). What theorem in the book did you use to answer the question?
7. True or false: If I can run an algorithm in polynomial time on a nondeterministic Turing machine, then I can run it in polynomial time on a single-tape Turing machine. Explain your answer.
8. Are the following problems in P? Justify your answers. (Hint: Theorem x.y in the book says so is good enough.)
   • PATH (Is there a path in a graph from vertex s to vertex t?)
   • The language A = {0ⁿ1ⁿ | n ≥ 1}. (Hint: A is context free.)

Homework 12

Problem	Comments
5.1	This is easy if you choose the correct undecidable problem to reduce from. I'll give you a hint: reduce from one of the undecidable languages related to CFGs. It also might be helpful to recall that the top of page 199 implies that SOMETHINGCFG is decidable iff SOMETHINGPDA is decidable.
5.3	Write a computer program to solve it. Oh wait. Never mind. But a little trial-and-error should yield a solution. I know there is a solution with 7 dominos. There may or may not be a shorter one. I tell you this so you don't give up too quickly.
5.2	Construct a TM that can recognize the complement of EQCFG. In other words, all strings that are not of the form in the definition of EQCFG. And remember, you only need to recognize.
5.4	If you can find a mapping from any non-regular language to any regular language, that would be proof that the statement is not true. Don't forget that a mapping reduction is computed using a Turing machine, so you have more power at your disposal than DFAs, CFGs, etc.
5.17	Provide a TM and explain why it works.
5.18	Reduce from the normal PCP. Thinking in terms of binary representations of things is a good start, but you need to be careful. It is easy to ensure that if an instance w of PCP has a match, then f(w) will have a match in BPCP. However, if you are not careful, it may be possible for f(w) to have a match in BPCP when w does not have a match in PCP.
5.23	Notice the iff. In other words, you need to prove both directions. And don't over think it. You don't need a fancy mapping--you just need to ensure that something in A maps to something in 0*1* and something not in A does not. It doesn't matter exactly WHAT strings you map to as long as that property holds.

Homework 13

Problem	Comments
7.7	You only need to prove closure under union. This one is really easy--You essentially need to re-prove an exercise from chapter 3 (for which a solution is given) with the added requirement to show that the polynomial time requirement is satisfied.
7.9	This one is really easy if you don't over think it.
7.20	Make sure to answer both questions, and do so separately. You may use the result of exercise 7.18 if you think it helps.
7.12	You have two choices: Give a NTM that decides the language. Define a certificate for the problem and explain how it can be used to verify that the two graphs are isomorphic. In both cases, you need to argue that they are polynomial-time. Notice that you only need to prove that it is NP, not that it is NP-complete.
7.21b	Make sure you show that it is both NP and NP-Hard. For the NP-Hard part, give a TM that computes the reduction and prove that it is indeed a reduction, and argue that it is a polynomial reduction. There is an easy reduction if you choose the right problem to reduce from.