assignments

Assignment 0

• Plunge into Chapter 0 of Sipser. Read and understand as much as you can.
• In class we'll go over the main ideas and any bits you found especially sticky.

Assignment 1

• Problems 0.3 ("Is the set..."), 0.7 ("For each part..."), 0.10 ("Find the error in the following proof that 2=1...") and 0.12 ("Show that every graph...") from Sipser (2nd ed.)
• Show that 1.2 + 2.3 + 3.4 + ... + n(n+1) = n(n+1)(n+2)/3 for all positive integers n (where "." denotes multiplication)
• Design a DFA that accepts strings formed from the alphabet {0, 1} if and only if they have either an even number of 1s or a number of zeroes congruent to 1 modulo 3 (or both).
• Design a DFA that accepts strings formed from the alphabet {0, 1} if and only if they have both an even number of 1s and a number of zeroes congruent to 1 modulo 3.

Assignment 2

• Finish reading chapter 1.
• For each of the two exercises, create a *.fa file using Jim's simulator along with some appropriate tests that demonstrates that machine. (I've set up the CGI script so that you can modify the _sample.fa file. Once it does what you want, copy/paste the text into a file on your computer, and submit it as part of your homework. Then reset the _sample machine so the next person isn't starting from yours.)
  • 1.6.i (a DFA with a 1 in odd positions) on page 84 (2nd ed)
  • 1.7.e (an NFA for 0*1*0+) also on page 84 (2nd ed). Note that "*" means "zero, one, two, or more times" while "+" means "one, two, or more times."
• Write a computer program in a language of your choice that implements a simple DFA of your choice. Please pick one that we have not done in class. You may use the python program that I demonstrated as a starting point and adapt it if you wish, or use any other language you like. This does *not* have to be a general purpose tool, just a simulation of a particular DFA. (If this feels too easy, simulate an NFA instead.)
• Do 1.14 ("Show that if M is a DFA that...") , 1.16. ("Use the construction given in Theorem 1.39 to ...").
• Also do two to get you thinking about the pumping lemma, 1.29b ("Use the pumping lemma to show that...") and 1.43 ("Let A be any languages. Define DROP-OUT(A) ...").

Assignment 3

• Read chapter 2.
• Browse through some of the "Parser Generator" links the Feb 8 notes, and start getting a feel for what tools like yacc flex etc are: what they take as input, what they produce as output, how they work, and how to use them. You don't need to submit anything on these yet; we'll talk more about them next week. (There will be a future assignment to pick one and explore it.)
• From Sipser chapter 1 : 1.54 (Consider the language F...), 1.55c,e,f (The pumping lemma says...),
• From Sipser chapter 2 : 2.9 (Give a context-free grammar...), 2.10 (Give and informal description...), 2.16 (Show that the class...), 2.17 (Use the results...), 2.21 (Let Σ = {a,b} ...)

Assignment 4

• If you haven't yet browsed through the parser generator tools from last assignment, do so. And if you'd like more choices, you can peruse either of the following lists of (a) lots of 'em, or (b) a bunch of 'em in python. (pyparsing may be a simple choice, with the 'elements' example.)
  • http://en.wikipedia.org/wiki/Comparison_of_parser_generators
  • http://nedbatchelder.com/text/python-parsers.html
• Pick one of them; install and test it on one of the examples it comes with.
• Using that tool, implement and test a simple CFG, such as one from Sipser such as paren matching.
• From Sipser: 2.31 ("Let B be the language..."), 2.44 ("If A and B are languages...").

Assignment 5

• From Sipser: 2.19, 2.24, 2.26, 2.33, 2.35.

Assignment 6

• Implement and test Sipser's example 3.7 with the vtm emulator. (If you'd rather write your own turing machine simulator rather than use vtm, that's OK too.)
• Design a turing machine that adds two base 2 numbers. (You can either have it recognize X+Y=Z expressions, or start from X+Y and generate X+Y=Z. Explain why these two things are essentially the same.)
• From Sipser: 3.8b (Give implementation-level...), 3.12 (A Turing maching with left reset...), 3.15 (Show that the collection of decidable...), 3.19.

Assignment 7

• From Sipser: 4.6 (Let B...), 4.10 (Let INFINITE_PDA...), 4.16 (PRove that EQ_DFA...), 4.18 (Let A and B be two disjoint...).
• Find the error in this proof

Assignment 8

• Read chapter 5
• Read sections 6.1 and 6.4
• 5.16, 5.23
• Give an example in the spirt of the recursion theorem of a program in a real programming language that prints itself out.

Assignment 9

• Where does Sipser's argument that Th(N,+) is decidable break down when we try to apply it to Th(N,+,x)?
• From Sipser: 6.2 (Show that any infinite...), 6.13 (For each m > 1...), 6.23 (Show that the set of incompressible strings is undecidable).
• Google and read about Chaitin's constant.

Assignment 10

• Finish reading chapter 7
• Do problem 7.26 (flip cards)
• Choose a classic NP problem, and implement a solution in a programming language of your choice. Show explicitly with various values for n that the solution takes an exponential number of steps.
• Demonstrate explicitly with your code that a solution can be verified in a polynomial number of steps.
• Explore and discuss the NP-complete Minesweeper pdf

final exam

• This exam is due by 10am next Mon.

term grade

• A place for overall comments.