Final review
The final will take place on Wednesday, December 18 at 2pm, in Trottier (room 1080 for last name Ase-Leh, 1090 for Leu-Zho). It will be 3 hours long and will be open book (so you can bring textbooks and other reference materials if you like).
1Material covered¶
All the lectures, except for the ones that are explicitly indicated to not be on the final. (Most notably, the last lecture on Gödel's incompleteness theorem is omitted.) For reference, the three main modules in this course are:
- Finite state systems
- Context-free languages
- The limits of computability
2Things to review¶
2.1Reductions¶
It seems that this class, as a whole, does not excel at reductions, so here's a review of how they work.
Suppose $P$ and $Q$ are problems. If $P \leq_m Q$, this means that if we could solve $Q$, then we could solve $P$. So, to perform the reduction, given an instance of the problem $P$, we transform it into a case of the problem $Q$.
More to come on reductions later.
3Structure of the final¶
There will be 6 questions, each worth 10 points. However, they will not be equally difficult! Some questions will actually be easy. Do not be worried by this.
The form of the questions will be as follows:
- Design a CFG for some CFL.
- Something about regular languages (but not just designing a simple FSM).
- Given a language, classify it into one of the following categories:
- Regular: provide a DFA/NFA as a proof.
- Context-free but not regular: provide a grammar as proof (or a PDA, but a grammar should be easier).
- Recursive but not context-free: provide an algorithm or Turing machine to generate it, and use a pumping lemma argument to show that it's not context-free.
- Computability theory: You'll be given 2 similar languages. One is RE, one is not. Prove which is which, via reductions.
- Show that a problem is undecidable (via reductions).
- 5 true/false questions with no explanation required. Could be about anything covered in the course (except non-testable stuff) - VALCOMPS, validity in first-order logic, etc.