CPSC 433
Spring 2006
Homework
General Instructions:
- The numbers refer to the textbook.
- Write clearly and legibly. Grading will be based on correctness,
clarity, and whether your solution is of the appropriate length.
- Don't forget to acknowledge all sources of assistance.
Unless otherwise instructed, you must write up your homework
on your own. Turn in your homework together with this
cover sheet.
- Homework is always due at the beginning of class.
Homework 6. Due 12:45 PM, Thursday, April 27, 2006.
- Exercise 9.1.3 (b). Read the solution to part (a) for help.
- Exercise 9.2.1
- Read the the statement of Exercise 9.2.3, especially the Hint.
(There is nothing to turn in.)
- Exercise 9.2.6 (a), (b) and (c), for both the r.e. languages and
for the recursive languages. (So there are 6 parts to this problem.)
Even though the solution for (a) is on the text web site, you must
write your solution in your own words.
- Exercise 9.3.4 (a) and (b)
Hint: Read the solution to part (d) to get an idea how to show a
language is not r.e. They show that L_e is reducible
to the given problem, i.e., the given problem is at least as hard
as L_e. Since L_e is not not r.e. (cf. Theorem 9.10), the given
problem is not r.e.
- Read the solution to Exercise 9.3.6. The point is that certain
things about Turing machines *are* decidable (e.g., how they behave
up to a certain point), even though properties of their languages
are not. (There is nothing to turn in.)
- Exercise 9.3.7 (a). Even though the solution is on the text web
page, you must write the solution in your own words.
- Exercise 10.1.6 (b) and (c). Even though the solution is on the
text web page, you must write the solution in your own words.
- Exercise 10.1.7 (b) and (c).
- Exercise 10.3.2
- Exercise 10.4.1. Even though the solution is on the
text web page, you must write the solution in your own words.
- Exercise 10.4.4 (a).
Homework 5. Due 12:45 PM, Tuesday, April 4, 2006.
- Exercise 7.3.2.
- Exercise 7.4.1 (b)
- Exercise 8.2.2 (c). Draw the TM's transition function as a
state transition diagram. Include an intuitive description of
how it works.
- Exercise 8.2.4 (a) and (b). It is particularly important to
write your solution in your own words!
- Consider the NTM in Exercise 8.4.2. Give all computations of the
TM on input 011, organized as a tree.
- Read the solution to Exercise 8.4.5. (There is nothing for you
to turn in for this.)
- *** this is the complete assignment ***
- PROGRAMMING ASSIGNMENT 2 to simulate a nondeterministic
Turing machine. Details are here. Unlike the
rest of HW 5, which is due April 4, it will be due April 13.
Homework 4. Due 12:45 PM, Tuesday, March 21, 2006.
For all problems that ask you to design a PDA, you must include
a prose description of the intuition of what your PDA is doing, i.e.,
what the different states represent. This will make it possible for
you to get extra credit.
- Refer to Exercise 6.1.1: Draw the generalized state transition
diagram for the PDA. Then show all the reachable ID's (in a tree
format similar to Fig. 6.3) when the input is 010.
- Exercise 6.2.1 (c).
- Exercise 6.2.2 (b).
- Exercise 6.2.6 (a).
- Exercise 6.3.2.
- Exercise 6.3.5 (b).
- Exercise 6.4.2 (b).
- Exercise 7.2.1 (b) and (c) and (e).
Homework 3. Due 12:45 PM, Tuesday, February 21, 2006.
- Give a context-free grammar for the language {a^i b^j c^k :
i > j + k}.
- Give a context-free grammar for the language {a^i b^j c^k :
i < j or i > k}.
- Exercise 5.1.2 (c)
- EXTRA CREDIT: Exercise 5.1.3
- Exercise 5.2.1 (c)
- Exercise 5.3.2 (the solutions are on line so be sure to
write your answer in your own words)
- Exercise 5.4.5 (b)
- Exercise 7.1.5
- Exercise 7.1.6
Homework 2. Due 12:45 PM, Tuesday, February 14, 2006.
- Exercise 3.1.1 (b) and (c)
- Exercise 3.1.2 (b)
- Exercise 3.2.3
- Exercise 3.2.4 (c)
- Exercise 4.1.1 (d), (e), and (f) (p. 129)
- Exercise 4.1.2 (d), (g), and (h)
- Exercise 4.1.4 (d)
- Exercise 4.2.6 (c)
- Exercise 4.2.13 (b)
- Exercise 4.3.2
- PROGRAMMING ASSIGNMENT to simulate a DFA. Details
are available here.
Homework 1. Due 12:45 PM, Tuesday, January 31, 2006.
- The Fibonacci numbers, F(0), F(1), F(2), ... are defined
recursively like this:
Base cases: F(0) = 0, F(1) = 1.
Recursive: For n > 1, F(n) = F(n-1) + F(n-2).
Prove using induction on n that for all n >= 0 and m >= 1,
F(n+m) = F(m)*F(n+1) + F(m-1)*F(n).
- Consider the set U of expressions defined recursively like this:
Base cases: The digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 are in U.
Recursive: Two combining operations are defined:
- If E1 and E2 are expressions (in U), then so is "E1 + E2".
- If E is an expression (in U), then so is "(E)".
Prove using induction on the number of combining operations used to
create the expression that every expression in U has an equal number
of left and right parentheses.
- Exercise 2.2.4, (b) and (c)
- Exercise 2.2.5, (a) through (d)
- Convert to a DFA the NFA of Figure 2.15 with n = 3.
Use the algorithm presented in class.
- Exercise 2.3.4, (b) and (c)
- Exercise 2.5.3, (a) and (b)