## Theory of Computation, Fall 2017

###

- Instructor: Wonhong Nam
- Class time: Wed 12:00-1:30pm and Fri 10:30-12:00am
- Office hours: Tue 2-3pm and Thur 3:00-4:00pm
- Tutor: ÀÌÅÂ¼ø (nrst136@naver.com)
- Tutor Office hours: Tue 6-7PM at 501

### Introduction

To understand computation, this course offers an introduction to the science behind computing by studying computation abstractly without worrying about specifics of programming languages and/or computing platforms. In particular, we will study (a) finite automata that capture what can be computed using constant memory, and define the class of regular languages useful for pattern matching languages; (b) the universal computational model of Turing machines, and the inherent limits of what can be solved on a computer (undecidability).
- Finite Automata, Regular Expressions, Regular Languages
- Pushdown Automata, Context-free Grammars, Context-free Languages
- Turing Machines
- Decidability

### Textbook

- Introduction to the Theory of Computation. Michael Sipser, 2nd or 3rd edition.

### Class notes

Chapter 0. Introduction [2-up] [4-up]
Chapter 1. Regular Languages [2-up] [4-up]
Chapter 2. Context-Free Languages [2-up] [4-up]
Chapter 3. The Church-Turing Thesis [2-up] [4-up]
Chapter 4. Decidability
Halting Problem

### Midterm stat.

- Avg.: 68.2/100
- 100: 2
- 99 - 90: 3
- 89 - 80: 10
- 79 - 70: 8
- 69 - 60: 2
- 59 - 50: 1
- 49 - 40: 3
- 39 - 30: 3
- 29 - 0 : 3

### Homework

Maintained by Wonhong Nam.