I’m attempting to study for my Automata final, which is going slowly, and not something I’m able to keep enthusiasm up about.
- I only need a 51 on the final to get the requisite B in the class, and given that every exam prior had a 15 point curve, I probably only really need a 36. A 57 or better (pre curve) translates into an A-.
- The PDA and Turing Machine portions of the exam are well in hand. I feel comfortable converting back and forth between them and a language definition. I personally find generating Turing Machines a lot of fun, and really interesting ways to make your brain work. They just take time, and I’ve had no issue on time in previous exams.
- Chomsky hierarchy of language is pretty much just a table and a vend diagram to remember. Pretty confident in that.
- Pumping lemma for PDAs. I’m sure this is going to be the part of the exam I blow, but it will probably only be one question. The pumping lemma proof on the last exam accounted for the majority of points I lost for that test.
- Halting problem proof. I ran through this prior to class the other day without notes, and I think I can reproduce it at will. About to go attempt to do that now again.
- Life of Alan Turing bonus question (a staple of Prof. Hayes’ final exams), I’ve got enough fun facts memorized to do ok on that.
- Computability. We did a bit on the partial recursive functions for the last class. I’m not sure which portions are actually askable. Possibly an enumeration of the 3 basis functions (Z, S, P), or the 3 operations (composition, primitive recursion, unbounded minimalization). We were already told we weren’t going to have to actually do the mechanics of these, given their level of horridness, and being introduced on the last day of class.
Guess it’s time to start playing with proofs from memory, and reread Alan Turing’s life synopsis a few more times.