Dates: 11/25/24 - 12/1/24. Test 2 in CBTF this week. No class on Friday in observance of Thanksgiving. The test covers material in Weeks 5 through 8 and Monday of Week 9. In particular, you should make sure you can:
State the definition of the class of context-free languages
Explain the limits of the class of context-free languages
Identify some context-free sets and some non-context-free sets
Use general constructions to prove closure properties of the class of context-free langugages.
Use counterexamples to prove non-closure properties of the class of context-free langugages.
Motivate the definition of a Turing machine
Trace the computation of a Turing machine on given input
Describe the language recognized by a Turing machine
Determine if a Turing machine is a decider
Given an implementation-level description of a Turing machine
Use high-level descriptions to define and trace Turing machines
Apply dovetailing in high-level definitions of machines
State the definition of the class of recognizable languages
State the definition of the class of decidable languages
State the definition of the class of co-recognizable languages
Apply a general construction to create a new Turing machine from an example one.
Formalize a general construction from an informal description of it.
Use general constructions to prove closure properties of the class of decidable langugages.
Use general constructions to prove closure properties of the class of recognizable langugages.
Give examples of sets that are decidable.
Give examples of sets that are recognizable.
Connect languages and computational problems
Describe and use the encoding of objects as inputs to Turing machines
Trace high-level descriptions of algorithms for computational problems
Describe common computational problems with respect to DFA, NFA, regular expressions, PDA, and context-free grammars.
Give high-level descriptions of Turing machines that decide common computational problems with respect to DFA, NFA, regular expressions, PDA, and context-free grammars.
Define and explain the definitions of computational problems, including the acceptance, language emptiness, and language equality problems for DFA, NFA, REX, CFG, PDA, and TM, as well as the halting problem for TM.
Trace the argument that proves the acceptance problem for Turing machines is undecidable and explain why it works.
Define computable functions, and use them to give mapping reductions between computational problems
Build and analyze mapping reductions between computational problems
Deduce the decidability or undecidability of a computational problem given mapping reductions between it and other computational problems, or explain when this is not possible.
State, prove, and use theorems relating decidability, recognizability, and co-recognizability.
Prove that a language is decidable or recognizable by defining and analyzing a Turing machines with appropriate properties.
To study for the exam, we recommend reviewing class notes (e.g. annotations linked on the class website, podcast, supplementary video from the class website), reviewing homework (and its posted sample solutions), and in particular *working examples* (extra examples in lecture notes, textbook examples listed in hw, review quizzes, discussion examples) and getting feedback (office hours and Piazza).