# CMSC 415: Theory of computation

## Fall 2018

## 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 9:30am, in Ruffner 352.

### Resources

### Homework

- For 23 Aug, good review: 0.3, 0.11, 1.3, 1.4c, 1.6 a/c/d/e/h and the same ones for 1.18, 1.16, 1.20
- For 4 Sep:
1.48 "...of the substrings 01 and 10...",
1.49ab "...1
^{k}y | y in {0,1)*...", 1.53 "...Show that ADD is not regular", 1.54 "Consider the language F..."; - For 6 Sep: Revisit 1.54; 2.1 "Recall the CFG G4...", 2.4 bce "Give context-free grammars...",
- For 11 Sep: 2.13 "Let G ... be the following grammar....", 2.14 "Convert the following CFG...", 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.23, 2.27 (above); and, 2.9 "... ai bj ck ...", 2.20 "Let A / B = ...".
- For 18 Sep: Carry over 2.23 and 2.20 (above); and, 2.10 "... recognizes the language A in Exercise 2.9", and look back at 2.20 and 2.21 (and other problems from Chapter 2) and see if PDAs give us a better angle on solving those problems.
- For 20 Sep: Finish the proof of 2.20 and continue thinking about PDAs; 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 | ...".