assignments

1. assignment 0 due Thu Sep 5

• Plunge into Chapter 0 of Sipser. Read and understand as much as you can.
  • In class Thursday we'll go over the main ideas and any bits you found especially sticky.
• Then start Chapter 1 : as much as you can mange of section 1.1.

2. assignment 1 due Tue Sep 10

• Problems from Sipser (2nd Ed.):
  • 0.3 ("Is the set..."),
  • 0.7 ("For each part..."),
  • 0.11 (The one about horses),
  • 0.12 ("Show that every graph...") and
  • 0.13 (Ramsey's Theorem). Can you do better than \( 1/2 \log_2 n \) (in general or for specific small \( n \) )?
• Show that \( 1 \cdot 2 + 2 \cdot 3+3 \cdot 4+ \cdots +n(n+1)= n(n+1)(n+2)/3 \) for all positive integers \( n \) .

3. assignment 2 due Tue Sep 17

• Finish reading chapter 1.
• Do Sipser 1.14 ("Show that if M is a DFA that...") and 1.16 ("Use the construction given in Theorem 1.39 to ...").
• Read about regex's as used by programmers in python or javascript. Explain which parts of the regex programming syntax are consistent with the math definition of a regular expression, which aren't, and why.
• Give and test regexes that match simple versions of either (a) a valid email address, or (b) a valid URL. You'll need to decide "simple" means, and do a bit of digging to decide what characters are allowed where. (Please don't just google this; see what you can come up with. I'm saying 'simple' because the complete rules can get pretty messy.)

For at least one of these DFA's

• (a) {0,1} with even number of ones OR multiple of three of zeros
• (b) {0,1} with even number of ones AND multiple of three of zeros
• (c) {0,1} with a 1 in every odd position in the string
• (d) The language matched by the regex 0*1*00* .

do the following two coding exercises :

• Create a *.fa file using Jim's simulator ; see the link at the left. (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.)
• Write some code in a language of your choice (e.g. Python) to simulate it yourself, including running some test cases and printing out the result.

4. Assignment 3 due Tue Sep 24

• Finish the \( \{ a^{2^n} : n \geq 0 \} \) question we started in class.
• From Sipser (2nd Ed.): 1.43 (on DROP-OUT), 1.53 (on ADD).
• From Sipser (2nd Ed.): 2.4 b,e,f (constructing grammars) and 2.5 for parts b, e, f of 2.4 (constructing PDAs).

5. assignment 4 due Tue Oct 1

• Do the two code parsing exercises from Jim's 2018 notes; however, parse the string "2+3*z" instead of the one given.
• Create a grammar for either (a) the sequence of key presses for a reverse polish calculator, or (b) a simple Lisp (for example something like this one).
• (optional) Read about Lark, a python library that implements a parsing engine. Install it and work through its JSON parser tutorial. (This is a tool that, like Lex & Bison, creates a parser for you from a context-free grammar specification.)

6. assignment 5 due Tue Oct 8

From Chapter 2 of Sipser (2nd Ed):

• 2.20. "Let \( A/B = ... \)"
• 2.31. "Let \( B \) be the language..."
• 2.36. "Give an example..."

One (or more!) of the following tougher ones:

• 2.23. "Let \( D =... \)"
• 2.37. "Prove the following stronger form..."
• 2.40. "Say that a language is prefix-closed..."
• 2.45. "Let \( A = ... \)"

7. assignment 6 due Tue Oct 15

• Using my yvtm (yaml virtual turing machine) spec as described at virtual turing machine, implement and test a turing machine simulator. You can use a language of your choice ... but python might be a simple choice. The YAML format has library support in most popular languages, so reading in the file shouldn't be a lot of work.
• Using your yvtm (or if you get stuck mine; ask) write Turing machine programs in the *.yvtm form for at least two of the following three machines :
  • recognize the language \(a^nb^nc^n\)
  • addition base 2, i.e. 101 + 111 = 1100
  • recognize strings of 0's and 1's which have an even number of 0's and either a multiple of 3 or a multiple of 5 number of 1's.
• Read chapter 3 in Sipser (for Thursday).
• From Sipser: 3.4 (definition of enumerator), 3.11 (doubly infinite tape).

8. Assignment 7 due Thu Oct 24

• From Sipser: 3.8b (implementation level TM), 3.12 (left reset), 3.15 (closure of decidable languages), 3.19 (infinite recognisable languages), 4.7 (Let T...), 4.18 (Let A and B...).
• Find the mistake in this proof.

9. Assignment 8 due Tue Nov 5

• Sipser: 5.3 (Find a match), 5.19 (Silly PCP), 5.21 (AMBIG_CFG), 5.31 (Collatz).

10. Assignment 9 due Tue Nov 12

Programming problem discussed in class:

• Choose a classic P problem. Implement a computer program in a language of your choice that solves it for various n, and show that the runtime is a polynomial.
• Do the same for a classic NP problem, but this time show that the runtime is exponential.
• Finally, demonstrate that a solution to that NP problem can be verified by a program that runs in polynomial time.

Sipser 7.26 (You are given a box...)

11. Assignment 10 due Tue Nov 26

• Translate the sentence "Every prime is expressible as the sum of two square numbers" into precise language for math statements given in Section 6.2. Is it a member of \( \mathcal{Th}( N, + , \times) \)?
• Sipser: 6.6 (Describe two Turing machines...), 6.13 (Integers mod m), 6.25 (Show that for any c...)

12. Assignment 11 due Mon Dec 16

• Do at least a couple of problems (of your choosing) from Chapter 10.
• Revisit one or more problem from an earlier assignment and submit an improved version.
• Submit some appropriate questions/work related to the topic for your presentation on Tuesday Dec 10th.