Homework for CS/MATH 300

CS/MATH 300 Home

Homework

Class Notes

Syllabus

Bibliography
This document was last modified on June 1, 2009.
Jump directly to Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10
The author of the textbook maintains a list of errata.

Week 1: Thursday

Reading Assignment for Thursday of First Week:

Read Chapter 0. (Everything after Section 0.1 should be review.)
Read Section 1.1.

Discussion Questions for Thursday of First Week:

Give state diagrams of deterministic finite automata recognizing the following languages. In all cases the alphabet is {0,1}.

(Chelsea) {w | w begins with a 1 and ends with a 0}.
(Ben) {w | w has length at least 3 and its third symbol is a 0}.
(Evan) {w | w doesn't contain the substring 110}.
(Kevin) {w | w contains at least two 0s and at most one 1}.
(Alec) {w | w contains an even number of 0s or exactly two 1s}.
( These are parts a, d, f, j, and l of 1.6.)

New material for Thursday of First Week:
(Evan) Explain the differences between an NFA and a DFA.
(Ben) Give an example of an NFA and show how it computes, by tracing through several accepting and non-accepting inputs.
(Chelsea) Present the formal definition of an NFA.
(Kevin and Alec) Present Theorem 1.39 on the equivalence of NFAs and DFAs.

Week 2: Tuesday

Homework Problems for Tuesday of Second Week:

Exercise 1.14:
Show that, if M is a DFA that recognizes language B, swapping the accept and nonaccept states in M yields a new DFA that recognizes the complement of B. Conclude that the class of regular languages is closed under complement.
Show by giving an example that, if M is an NFA that recognizes language C, swapping the accept and nonaccpet states in M doesn't necessarily yield a new NFA that recognizes the complement of C. Is the class of languages recognized by NFAs closed under comlpement? Explain your answer.

Let
D={w | w contains an equal number of occurrences of the substrings 01 and 10}.
Thus 101 is in D because 101 contains a single 01 and a single 10, but 1010 is not in D because 1010 contains two 10s and one 01. Show that D is a regular language by constructing a finite automaton that recognizes D. (This is Problem 1.48, or 1.41 in the old text.)

Reading Assignment for Tuesday of Second Week:

Read Section 1.2.
Read Section 1.3.

Discussion Questions for Tuesday of Second Week:

Give NFAs with the specified number of states recognizing each of the following languages. In all cases the alphabet is {0,1}.

(Alec) Exercise 1.7 b.
(Evan) Exercise 1.7 e.
(Ben) Exercise 1.10 c.

(Chelsea) Exercise 1.16 b.
(Kevin) Convert the following NFA to a DFA:

(The following are parts b, d, f, j, and l of Exercise 1.18.) Give regular expressions generating the following languages. In all cases the alphabet is {0,1}.

(Evan) {w | w contains at least three 1s}.
(Alec) {w | w has length at least 3 and its third symbol is a 0}.
(Kevin) {w | w doesn't contain the substring 110}.
(Chelsea) {w | w contains at least two 0s and at most one 1}.
(Ben) {w | w contains an even number of 0s or exactly two 1s}.

New material for Tuesday of Second Week:
(Evan, Chelsea) Describe the idea behind the proof of Lemma 1.60, define GNFAs.
(Ben) Example 1.66.
(Alec) Example 1.68.
(Kevin) Exercise 1.21 b.

Week 2: Thursday

Homework Problems for Thursday of Second Week:

Problems 1.31 and 1.32 (Problems 1.24 and 1.25 in old text).

Reading Assignment for Thursday of Second Week:

Read Section 1.4.

Discussion Questions for Thursday of Second Week:

(Ben) (The following is Exercise 1.15.) Give a counterexample to show that the following construction fails to prove Theorem 1.49, the closure of the class of regular languages under the star operation. (In other words, you must present a finite automaton, N₁, for which the constructed automaton N does not recognize the star of N₁'s language.) Let N₁ = (Q₁, Sigma, delta₁, q₁, F₁) recognize A₁. Construct N = (Q₁, Sigma, delta, q₁, F) as follows. N is supposed to recognize A₁^*.

The states of N are the states of N₁.
The start state of N is the same as the start state of N₁.
F = {q₁} union F₁. The accept states F are the old accept states plus its start state.
Define delta so that for any q in Q and any a in Sigma_epsilon:

delta(q,a) = delta₁(q,a) if q is not in F₁ or a is not equal to epsilon;
delta(q,a) = delta₁ union {q₁} if q is in F₁ and a = epsilon. (Suggestion: Convert this formal construction to a picture, as in Figure 1.50.)

(Chelsea - part a, Alec - part b) Exercise 1.19, parts a and b.
(Kevin) Part c of Exercise 1.28.
(Evan) (The following is Problem 1.36.) Let B_n = { a^k | where k is a multiple of n}. Show that for each n >= 1, the language B_n is regular.

New material for Thursday of Second Week:
(Ben) Theorem 1.70.
(Chelsea) Example 1.73.
(Kevin - part a, Evan - part b, Alec - part c) Exercise 1.29.

Week 3: Tuesday

Homework Problems for Tuesday of Third Week:

Prove that the language {w | w is a palindrome} over the alphabet {0, 1} is not regular. (A palindrome is a string that reads the same forward and backward.)
Problem 1.35.

Reading Assignment for Tuesday of Third Week:

Read Section 2.1

Discussion Questions for Tuesday of Third Week:

(All)Convert the NFAs from Figures 1.6 and 1.42 (Figures 1.4 and 1.21 in old text) to regular expressions.
(All) Exercise 1.30.
Exercise 1.55 (Chelsea - part c, Evan - part e, Kevin - part g, Alec - part h, Ben - part i)

New material for Tuesday of Third Week:
(Alec) Define context-free grammars (CFGs) and give an example.
(Chelsea) Discuss process of designing CFGs.
Parts d(Evan) and e(Kevin) of Exercise 2.4.
(Ben) Discuss ambiguity and do exercise 2.8
(All) Consider the grammar with rules
S -> aaB
A -> bBb|epsilon
B -> Aa.
Show that the string aabbabba is not in the language generated by this grammar.

Week 3: Thursday

Homework Problems for Thursday of Third Week:

Exercise 2.13.

Reading Assignment for Thursday of Third Week:

Read Section 2.2.

Discussion Questions for Thursday of Third Week:

(All) Last problem from new material on Tuesday of Third Week.
(Alec) Exercise 2.3 part o.
Exercise 2.6 (Ben - part b, Chelsea - part c, Kevin - part d)
(Evan) Exercise 2.16.

New material for Thursday of Third Week:
(Kevin) Theorem 2.9.
(Alec) Example 2.10.
(Evan) Problem 2.26.
(Ben) Introduce pushdown automata (definition 2.13 and example 2.14).
(Chelsea) Example 2.16.
(All) Parts b, c, e of Exercises 2.5 and 2.7.
(Alec) Lemma 2.21.
(Kevin) Proof idea for Lemma 2.27.

Week 4: Tuesday

Homework Problems for Tuesday of Fourth Week:

Exercise 2.14.
Exercise 2.17.

Reading Assignment for Tuesday of Fourth Week:

Read Section 2.3.

New material for Tuesday of Fourth Week:

New material from Thursday of Third Week, starting with Ben introducing pushdown automata.
(Evan) Exercise 2.18.
(Chelsea) Exercise 2.11.
(Alec & Kevin) Theorem 2.34.

Week 4: Thursday

Homework Problems for Thursday of Fourth Week:

Exercise 2.2.
Exercise 2.12.

Reading Assignment for Thursday of Fourth Week:
Finish reading Section 2.3.

Exam 1 will be due on Tuesday of Fifth Week.

Discussion Questions for Thursday of Fourth Week

(Chelsea) Exercise 2.11.
(Ben) Give an informal description and a state diagram of a PDA for the language {w | w contains more 1s than 0s}, over the alphabet {0, 1}.
(Pam) Convert the PDA that processes sequences of if's and else's into an equivalent CFG.

New material for Thursday of Fourth Week:

(Alec & Kevin) Theorem 2.34.
(Evan) Problem 2.18.
(Ben, Chelsea) Problem 2.30, parts b and c.

Week 5: Tuesday

No Class. Exam 1 is due.

Week 5: Thursday

Homework problem for Thursday of Fifth Week:
Convert the PDA for the language of palindromes over {0, 1} into an equivalent CFG.

Reading Assignment for Thursday of Fifth Week:
Read Sections 3.1 and 3.2.

Discussion Questions/New Material for Thursday of Fifth Week:

(Chelsea) Introduce definitions (Turing machine, various types of configurations, Turing-recognizable, Turing-decidable)
(Ben) Example 3.7.
(Alec) Example 3.9.
(Evan) Example 3.11.
(Kevin) Example 3.12
(Ben) Exercise 3.2 (d).
(Alec) Exercise 3.5.
(Chelsea, Kevin, Evan) Exercise 3.8, giving higher-level descriptions.
(All) Look at examples #1-6 of Turing Machines. Describe the languages recognized by these machines.

Week 6: Tuesday

Homework problems for Tuesday of Sixth Week:

Problem 3.11.

Reading Assignment for Tuesday of Sixth Week:

Read Sections 3.3 and 4.1.

Discussion questions & new material for Tuesday of Sixth Week:

(Kevin) Problem 3.15 (b), (c).
(Evan) Problem 3.15 (d), (e).
(Ben) Problem 3.16 (b), (c).
(Chelsea) Problem 3.16 (d).
(Alec) Problem 3.22.
(Kevin) Theorem 4.1.
(Ben) Theorem 4.2.
(Chelsea) Theorem 4.3.
(Alec) Theorem 4.4.
(Evan) Theorem 4.5.

Week 6: Thursday

Reading Assignment for Thursday of Sixth Week:

Read Sections 4.2 and 5.1.

Discussion Questions and New Material for Thursday of Sixth Week:

(Chelsea) Exercise 4.2.
(Ben) Exercise 4.3.
(Kevin) Exercise 4.5.
(Evan)Problem 4.9.
(Alec) Problem 4.15.
(Chelsea) Problem 4.23.
(All) Theorem 4.11.
(Ben) Corollary 4.18.
(Evan) Theorem 4.22.
(Alec) Corollary 4.23.
(Kevin) Theorem 5.1.

Week 7: Tuesday

Homework problems for Tuesday of Seventh Week:

Problems 4.12, 4.19, 4.24, 4.26.

Reading Assignment for Tuesday of Seventh Week:

Read Section 5.1, 5.3.

Discussion Questions and New Material for Tuesday of Seventh Week:

(Alec) Theorem 5.2.
(Chelsea) Theorem 5.3.
(Ben) Theorem 5.4.
(Evan) Exercise 5.1.
(Kevin) Exercise 5.2.
(Alec) Problem 5.13.
(Evan) Theorem 5.22 & Corollary 5.23.
(Kevin) Example 5.24.
(Ben) Example 5.26.
(Chelsea) Exercise 5.5.
(All) Problem 5.28.

Week 7: Thursday
Homework problem for Thursday of Seventh Week:
Problem 5.9.

Reading Assignment for Thursday of Seventh Week:
Sections 7.1, 7.2.

Discussion Questions and New Material for Thursday of Seventh Week:
(All) Come up with a nicely written solution to Problem 5.13.
(Chelsea) Exercise 5.5.
(Alec) Definitions 7.2, 7.5 and examples.
(Kevin) Definition 7.7 and example involving language A = {0^k1^k| k >= 0}.
(Ben) Theorem 7.8.
(Evan) Definition 7.9 & Theorem 7.11.
(Alec) Exercise 7.5.
(Chelsea) Exercise 7.6.
(Kevin) Exercise 7.7.
(Ben) Exercise 7.11.
(Evan) Show that O(t(n)b^t(n)) = 2^O(t(n)).
(All) If A is in NP, is the complement of A necessarily in NP? Why or why not?

Week 8: Tuesday

Homework problems for Tuesday of Eighth Week:

Problems 5.22 and 5.24.

Reading Assignment for Tuesday of Eighth Week:

Read Sections 7.3 and 7.4.

Discussion Questions and New Material for Tuesday of Eighth Week:

(Chelsea) Exercise 7.6.
(Kevin) Exercise 7.7.
(Alec) Theorem 7.14.
(Evan) Theorem 7.15
(Ben) Theorem 7.16
(Kevin) Theorem 7.24.
(Chelsea) Theorem 7.25
(Evan) Exercise 7.8.
(Alec) Exercise 7.10.
(Ben) Exercise 7.11.
(All) If A is in NP, is the complement of A necessarily in NP? Why or why not?
(All) Problem 7.14.
(All) Problem 7.15.

Exam 2 will be given out Thursday of Eighth Week, and will be due by 9 AM Thursday of Ninth Week.

Week 8: Thursday

Homework Problems for Thursday of Eighth Week:
Exercise 7.9 and Problem 7.12

Reading Assignment for Thursday of Eighth Week:

Read Sections 7.4, 7.5

Discussion Questions and New Material for Thursday of Eighth Week:

(All) What can you find out about the closure of NP under complementation?
(Ben) Exercise 7.11.
(All) Problem 7.14.
(All) Problem 7.15.
(All) Show that primality testing is solvable in polynomial time if we use a unary encoding rather than a binary encoding for numbers, In other words, show that the language UNARY_PRIMES = {1ⁿ | n is prime} is in P. (Suggestion: Think about designing a 2-tape TM to decide UNARY-PRIMES and use a technique similar to the Sieve of Eratosthenes)
(Alec) Theorem 7.31.
(Chelsea) Theorem 7.32.
(Kevin & Evan) Theorem 7.37.
(Ben) Theorem 7.42.
(Alec) Theorem 7.56.
(Chelsea) Exercise 7.31.

Week 9: Tuesday
Reminder: NO class today.
Exam 2 is due Thursday by 9 AM.
Week 9: Thursday

Reading Assignment for Thursday of Ninth Week:
Sections 8.1, 8.2 and 8.4.

Discussion Questions and New Material for Thursday of Ninth Week:

The last three questions from Thursday of Week 8.
(Evan) Examples 8.3 and 8.4.
(Kevin) Theorem 8.5.

Week 10: Tuesday

Reading Assignment for Tuesday of Tenth Week:

Read Sections 8.4, 8.5, and 9.1.

Homework Assignment for Tenth Week:
Problems 7.29, 7.30, and 8.17.

Discussion Questions and New Material for Tuesday of Tenth Week (Maybe an ambitious list!):
(Ben) Definition 8.17 and Example 8.18.
(Alec) Example 8.19.
(Kevin) Definition 8.20 and the discussion of the extension of Savitch's Theorem for sublinear space bounds.
(Chelsea) Definitions 8.21 and 8.22.
(Evan) Theorem 8.23 and Corollary 8.24.
(Ben) Theorem 8.25 and Corollary 8.26.
(All) Problem 8.8.
(All) Problem 8.17.
(All) Problem 8.25.
(Alec) Definition 9.1 and Example 9.2.
(Kevin) Theorem 9.3.
(Chelsea) Corollaries 9.4 and 9.5.
(Evan) Corollaries 9.6 and 9.7.
Definiton 9.8 and Example 9.9
Theorem 9.10.
Corollaries 9.11, 9.12, and 9.13.

The take-home final will be distributed in class on Thursday, and will be due Tuesday, June 9.

This page is maintained by Pamela Cutter (pcutter{at}kzoo{dot}edu).