- 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.

- 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 \) .

- 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.

- 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).

- 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.)

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 = ... \)"

- 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).

- 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.

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

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...)

- 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...)

- 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.