# CMSC 415: Theory of computation

## Fall 2016

## Prof. Blaheta

Welcome to CMSC 415! Computation theory is an exploration of the question of what it even means for something to be computable. Some of the earliest results that can now be identified as computer science—at the time seen as mathematical or philosophical facts—are in the area of theory of computation. Other areas of theory are questions that remain open after more than a half-century of work. In this course, we will ask some of these questions and develop an appreciation and understanding of the answers that the early computer scientists produced for them.

The textbook for this course is Michael Sipser, Introduction to the theory of computation. Either 2nd or 3rd edition is fine. (2e: ISBN 978-0-534-95097-2; 3e: ISBN 978-1133-18779-0)

This course meets TR at 2pm, in Ruffner 352.

### Resources

### Homework

- For 6 Sep: 1.53 "...Show that ADD is not regular", 1.54 "Consider the language F..."; 2.1 "Recall the CFG G4...", 2.4 bce "Give context-free grammars...", 2.13 "Let G ... be the following grammar....", 2.14 "Convert the following CFG..."
- For 8 Sep: Carrying over 2.13, 2.14 (see above); and, 2.21 "...twice as many a's as b's", 2.23 "Show that D is...", 2.27 "... G is ambiguous ...".
- For 13 Sep: Carry over 2.21, 2.23, 2.27 (above); and, 2.9 "... ai bj ck ...", 2.20 "Let A / B = ...".
- For 15 Sep: Carry over 2.20 (above); and, 2.10 "... recognizes the language A in Exercise 2.9", and look back at 2.20 and 2.21 and see if PDAs give us a better angle on solving those problems.
- For 20 Sep: Carry over 2.20 again; and, 2.30ad "Use the pumping lemma... ", 2.31 "Let B be the language of all palindromes...", 2.32 "Let Σ = {1,2,3,4} ...", 2.33 "Show that F={ aibj | ...".
- For 22 Sep: Wrap up 2.33; and, 3.1acd "...configurations that M2 enters...", 3.2bcde "...configurations that M1 enters...", 3.8b "Give implementation-level...", 3.9a "...Show that 2-PDAs...".
- For 27 Sep: 3.11 "... doubly infinite tape ...", 3.12 "... left reset ...", 3.13 "... stay put instead of left ...", 3.20 "... TMs that cannot write on ...".
- For 25 Oct:
4.3 "Let ALL
_{DFA}= ...", 4.4 "Let Aε_{CFG}= ...", 4.10 "Let INFINITE_{PDA}..." (not DFA, which is 4.9), 4.16 "Prove that EQ_{DFA}is ..." - For 27 Oct:
4.15 "...R is a regular expression ... 111 ...",
5.1 "... EQ
_{CFG}...", 5.9 "Let T = {<M> | M is ..." - For 8 Nov: 7.6 "... P is closed under ...", 7.7 "... NP is closed under ...", 7.9 "A triangle ...", 7.21/22 "Let DOUBLE-SAT = ...", 7.14/15 "... P is closed under the star operation ..."
- For 10 Nov: Carry over 7.21/22 from before, and: 7.26/28 "... box and collection of cards ..." 7.30/32 "... Minesweeper ..."

### Presentations

- 15 Nov: David and Mija, information theory
- 17 Nov: Jonathan and Olivia, probabilistic algorithms
- 22 Nov: Alec and Asa, parallel algorithms
- 29 Nov: Nick and Scott, approximation algorithms
- 1 Dec: Finn and Michael, space complexity

### Classroom stuff

- 23 Aug: board
- 25 Aug: left front side back
- 30 Aug: left front side back
- 1 Sep: left front side back
- 6 Sep: left front side-left side-right back
- 8 Sep: First batch: left side back-left back; Second batch: front right side back
- 13 Sep: left right side back
- 15 Sep: left right
- 20 Sep: left front right side back-left back-right
- 22 Sep: left right side back-left back-right
- 27 Sep: left front side back
- 6 Oct: left middle right
- 11 Oct: left middle right
- 13 Oct: board
- 25 Oct: left right side back-left back-right
- 27 Oct: left right side back
- 1 Nov: board
- 3 Nov: left right
- 8 Nov: left middle right side back-left back-right
- 10 Nov: left middle right