Chapters 8, 9, 10 and Context-Sensitive Grammars

General: Study suggested exercises for each chapter – most (but not all) are *’d and have solutions online. Read the breakout boxes and understand the concepts that they convey, with the most important being on pages 318, 322, 323, 390, 397, 435, 436).

Chapter 8: Know lectures and examples from Chapter 8, particularly TM programming lectures, slides (the handwritten ones) from week 9; I will ask you about one or more of these TM programs or something very similar., to include defining a TM. Study the examples from Chapter 8, most of which are “constructive”. From 8.5, know 8.5.1 and 8.5.2 — I won’t ask questions or make assumptions about the other sections of 8.5 (this includes not being asked about suggested exercise 8.5.1).

Chapter 9: Know the definitions of recursively enumerable and recursive languages, as well as their relationships to (un)decidability, and to the unrestricted and context sensitive languages (October 27 lecture — not in book), context free languages, and regular languages. I will probably ask you to give a context sensitive grammar. Know how a property of context sensitive grammars relate to decidability and recursive languages. Understand the diagonalization and universal languages, and the concept and procedure for TM encoding into binary. Know the undecidable problems of section 9.3 and 9.5, and throughout 9.2 and 9.3, know the proof sketches of theorems (often given in terms of constructing one TM from another). I may ask you about the definition of Post’s Correspondence Problem (section 9.4.1 and the suggested exercise for that subsection), but not other sections of 9.4).

Chapter 10: Know definitions and relationships between P, NP, and NP-complete from 10.1. What is the relationship to the (un)decidable problems? Know polynomial-time reduction too. Does a polynomial reduction have to be by a deterministic TM, or is it assumed to be from an NTM? Know the SAT problem (10.2), and watch the good tutorial on Cook’s theorem that is posted under week 12 on Brightspace. Grasp the big picture, and I may ask about one of the component encodings in the constructive proof of Cook’s Theorem. Know what the other NP-complete problems are from 10.3 and 10.4, not just the labels, but their definitions too, but you don’t need more than surface understanding of the proofs.