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, 0.7, 0.11 and 0.12 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 (or both).

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.
• 1.14, 1.16.

Assignment 3

• From Chapter 1: 1.29b, 1.43, 1.53, 1.54, 1.64.
• Read: 2.1 and 2.2.

Assignment 4

• Browse the "EBNF" and "Parser Generator" resources on the feb 19 page.
• Pick one of the parser generators (or one in another programming language) to explore. Install it, and run a simple example from it's documentation. One way to do this is to adapt the Bison example I showed in class (see code/bison) to implement the infix grammar, rather than the RPN I did in class. Describe what you did and how it went, and upload your code and some sample input/output.

Assignment 5

• Sipser: 2.9, 2.10, 2.29, 2.30a, 2.31 and one of 2.21 - 2.24.
• Prove Matt proving Sipser wrong wrong. First parse that sentence, and then find the flaw in my counterargument to 1.64b:
  • Let M be a machine with exactly k states that recognises a language A. Claim: If A contains all words of length at most k then is empty.
  • Proof (by "minimal criminal"). Suppose, for a contradiction, that s is a shortest word in . We know that s must have length at least k+1 because all shorter words are in A. The word s might fail for two reasons. Case 1: it ends in a non-accept state, and Case 2: it has no arrow to follow after some incomplete portion of the input.
    • Case 1. As there are k states and s has length at least k+1, there must be a repeated state somewhere during the rejection of s. If s has the form xyz where y represents the portion read between two occurrences of a repeated state, then xz is a shorter word than s that also ends in a reject state. This contradicts our choice of s.
    • Case 2. Let q be state that M is in immediately before s is rejected (i.e. q is the state without the arrow needed to continue processing s). The state q must be reachable in at most k-1 steps (it can be reached, because s reaches it, and as there are k states removing any sections between repeated states in the processing of s leaves a path with at most k-1 arrows). Make a new word t of length at most k that gets to q in at most k-1 steps and then has the symbol that forced M to reject s. The word t is rejected, again contradicting our choice of s.
  • Therefore has no shortest word and hence no words at all. QED
  • Sipser (1.64b) asks us to show that the statement "if is nonempty then contains some string of length at most k" is not true. However, I seem to have proved that it is. Ooops.

Assignment 6

• Create a multipy.vtm turing machine that multiplies two numbers, analogous to the add.vtm machine at code/vtm . (See the march 10 class notes for details about vtm.)
• Or create a turing machine that does addition with ascii digits base 10, i.e. "13 + 8" turns into "21".
• From Sipser: 3.10, 3.14, and one part of your choice from 3.15

Assignment 7

• 4.6, 4.10, 4.16, 4.18.

Assignment 8

• 5.16, 5.23, 6.22
• Give an example in the spirt of the recursion theorem of a program in a real programming language that prints itself out.
• Consider the following expression.
  • ∀z∃x∃y[x×x + y×y = z×z]
  • Is it a sentence in Th(N, + ,×) ?
  • What does it say in English?
  • If it is a sentence, is it a true sentence?

Assignment 9

• 7.5, 7.9, 7.26
• Check one of the
   

  Final Assignment

  • 1.41, 2.30d, 3.13, 4.19, 5.9, 7.21, 10.2, 10.6
   

  course grade

  • ... will be posted here.
  http://cs.marlboro.edu/ courses/ spring2008/formal_languages/ special/assignments
  last modified Thursday February 3 2011 1:07 am EST