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