Assignments

Assignment 0, Prepare for discussion at Lecture 2. Not to be handed in or graded.

Assignment 0 is intended to be somewhat self-diagnostic. If these concepts are unfamiliar then you may be unprepared for this course.

All problems are from Sipser:

1. Sipser 0.1 d,e,f
2. 0.2 d,e,f
3. 0.3 f
4. 0.7 (note: part c is subtle)
5. 0.8

Assignment 1, due at Lecture 3

Sipser (numbers in [] are for first edition)

1. 1.3 [1.3] (Draw DFA)
2. 1.4g [new] (Construct intersection)
3. 1.5d [new] (Complement)
4. 1.31 [1.24] (Closed under reverse)
5. 1.32 [1.25] (Correct sums)

Assignment 2, due Lecture 5

Sipser:

1. 1.16 (b) [1.12(b) in 1st edition]
2. 1.21(a) [1.16(a)]
3. 1.46(a) [not in 1st edition]
4. 1.51 [1.34] Indistinguishable by L is an equivalence relation.

Assignment 3, due Lecture 7

Sipser 2nd edition [first edition]:

1. 1.52 [1.35] Myhill-Nerode theorem. Please answer in your own words; the 2nd edition contains a sample solution.
2. 2.2 [2.2]
3. 2.18 [2.17]
4. 2.35 [2.20]

Assignment 4, due Lecture 9

Sipser 2nd edition [first edition]:

1. 2.30 a,d [2.18 a,d]
2. 2.22 [2.26] Hint: Focus on how two strings can be different. Two strings can be different if they are different lengths, or if there is some corresponding position where they differ. Your solution only needs to find a single difference. I have seen understandable solutions that use either a PDA or a grammar to define the language. As a warm up problem it may be useful to find a description for w#x#y#z such that |w| = |y|.
3. 3.6 [3.6]

Assignment 5, due Lecture 13

Sipser 2nd edition

1. 3.18 [3.16]
2. 4.6 [4.7] (diagonalization, {0,1}^\omega is not countable)
3. 4.17 [4.17] (C is Turing-recognizable if there is a decidable language D such that C = {x| \exists y . <x,y> \in D})

Assignment 6, due Lecture 15 (may be supplemented)

Sipser 2nd edition [1st edition]

1. 4.18 [4.18] (any two disjoint co-Turing-recognizable languages are separated by a decidable language)
2. 5.12 [?]
3. 5.28 [5.22] (Note: sample solution is given in 2nd edition; however collaboration policy applies!)
4. 5.30 [not in 1st edition]

Assignment 7, due Lecture 17

New assignment 7: primrec.pdf MY.hs NaturalPR.hs

pdf file [assignment may be revised for this class offering]

Assignment 8, due Lecture 19

Here is the updated pdf file.

Tim Sheard's calculator is http://hackage.haskell.org/package/LambdaCalculator

The Haskell Platform is http://hackage.haskell.org/platform/

(note: A sample solution for an earlier version of this assignment is available here; however the collaboration policy applies!)

Assignment 9, Do not hand in.

Supplemental assignment pdf file.