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: 이태순 (firstname.lastname@example.org)
- Tutor Office hours: Tue 6-7PM at 501
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
- Introduction to the Theory of Computation. Michael Sipser, 2nd or 3rd edition.
Chapter 0. Introduction [2-up] [4-up]
Chapter 1. Regular Languages [2-up] [4-up]
Chapter 2. Context-Free Languages
Chapter 3. The Church-Turing Thesis
Chapter 4. Decidability
- If you copy your friend's homework, you may have a penalty of 100%.
- Homework 1- due: 9/22
- Homework 2- due: 10/11
Maintained by Wonhong Nam.