This course will focus on fundamental mathematical models of computation. We will be interested in both the inherent capabilities and limitations of these computational models as well as their relationships with formal languages. Rigorous arguments and proofs of correctness will be emphasized. Particular topics to be covered include:
김용곤, 조유정, 연주영.
CS204 Discrete Mathematics.
To test your mathematical background, you can skim through Sections 1.2 and 1.3 of the textbook. You might not be able to produce all the details from memory, but almost all of it should look like something you used to know.
The class meets Monday, Wednesday, and Friday from 14:00 to 14:50 in lecture hall 102 in building N1. Lectures are given in English.
The final grade will be composed as follows (small changes reserved):
Attendance will be taken in nearly every class. If you miss at most 5 lectures, you receive 10 attendance points. For 6 missed lectures, you receive 9 attendance points, and so on. For 10 or more missed lectures you receive no attendance points.
Students who take CS322 for the second time cannot receive a grade better than A-.
We will have a midterm exam and a final exam.
The midterm exam is on October 25, from 14:00 to 16:00, in lecture hall 1501 in E3-1 (not in our usual classroom, and not even in the same building!).
The final exam is on December 20, from 14:00 to 16:00, in lecture hall 1501 in E3-1 (not in our usual classroom, and not even in the same building!).
Here is a rough list of what we will cover in each week of the semester.
| Week 1 | Strings, languages, DFA |
| Week 2 | Product construction, closure |
| Week 3 | No class (Chuseok week) |
| Week 4 | Regular expressions, NFA |
| Week 5 | Equivalence of DFA and NFA, Epsilon transitions, equivalence of regular expressions and DFA |
| Week 6 | Proving languages non-regular |
| Week 7 | Context-free grammars and languages |
| Week 8 | Midterm exam week |
| Week 9 | Chomsky normal form |
| Week 10 | Pumping lemma for CFL |
| Week 11 | Recursive and push-down automata |
| Week 12 | Turing machines |
| Week 13 | Decidability and the Halting Problem |
| Week 14 | Reductions and Rice's Theorem |
| Week 15 | Reserve |
| Week 16 | Exam week |
We have head-banging sessions for small groups of students. During those sessions, you solve problems in a team of two or three students, present your solution on the blackboard, and discuss the homework solutions.
The head-banging sessions will be held in Korean (foreign students are exempted).
At the beginning of the semester, the head-banging sessions are optional. They will be required for students who do not do well enough on the first quiz.
The head-banging sessions are scheduled as follows:
The current assignment of students to the four head-banging sessions are here.
We have a bulletin board on the Noah server. We will also try out Glassboard this semester. I will post announcements on both boards. You can ask questions on either board. Both Korean and English are acceptable :-), but you make it easier for me if you write in English.
You are responsible for checking the announcements regularly. This is easier if you install the Glassboard app for iPhone or Android, as it will notify you when a posting appears on the board.
We will use the free textbook Introduction to Theory of Computation by Anil Maheshwari and Michiel Smid.
You can download the PDF file of the book here.
Some other books on automata, formal languages, and the theory of computation are:
The material covered in the lectures so far ("Book" is our textbook, "HMU" is Introduction to Automata Theory, Languages, and Computation by Hopcroft, Ullman, and Motwani).
| 09/02 | Introduction, History | Book 1.1, slides |
| 09/04 | Alphabets, Strings, Countable sets | notes |
| 09/06 | Set of all languages is uncountable, Finite Automata | Book 2.1 |
| 09/09 | Formal definition of Automaton, examples | Book 2.2 |
| 09/11 | Formal definition of Computation, regular languages, operations on languages | Book 2.3 |
| 09/13 | Closure under union and intersection, NFA introduction | Book 2.3, 2.4 |
| 09/23 | Formal definition of NFA, NFA is equivalent to DFA | Book 2.4, 2.5 |
| 09/25 | JFLAP, Closure under the regular operations | Book 2.6, jflap |
| 09/27 | Introduction to regular expressions | Book 2.7 |
| 09/30 | From DFA to regular expression | notes |
| 10/02 | Closure under reversal and homomorphisms | |
| 10/04 | Suffix languages and the Myhill-Nerode Theorem | notes |
| 10/07 | Proof of Myhill-Nerode Theorem, Examples of non-regular languages | |
| 10/09 | No class (Hangul day) | |
| 10/11 | Using closure properties to prove non-regularity, pumping lemma | notes, Book 2.9 |
| 10/14 | Algorithms on regular languages | notes |
| 10/16 | Context-free grammars and languages | Book 3.1, 3.2 |
| 10/18 | Regular languages are CFL, Chomsky Normal Form | Book 3.3, 3.4 |
| Midterm exam on October 25, 14:00~16:00, room 1501 | ||
| 10/28 | Example of conversion to Chomsky Normal Form | Book 3.4 |
| 10/30 | Push-down Automata | Book 3.5, 3.6 |
| 11/01 | Left-most derivations, Parse Trees, Ambiguous grammars | HMU 5.1.4, 5.1.6, 5.2.1, 5.2.2 |
| 11/04 | Equivalence of CFG and PDA | Book 3.7 |
| 11/06 | Pumping Lemma for CFL and not context-free languages | Book 3.8 |
| 11/08 | Closure properties of CFL: Union, concatenation, Kleene-closure, intersection, difference, reversal, homomorphism | |
| 11/11 | Intersection of CFL and regular language is CFL, recursive-descent parser, parser generator with flex and bison | |
| 11/13 | Algorithms for CFL, CYK Parsing algorithm | Notes |
| 11/15 | No class (Freshmen interviews) | |
| 11/18 | Introduction to Turing machines | Book 4.1, 4.2 |
| 11/20 | Examples of Turing machines | Book 4.2 |
| 11/22 | No class | |
| 11/25 | Multi-tape Turing machines, Church-Turing thesis | Book 4.3, 4.4 |
| 11/27 | Decidability, ATM and Halt are undecidable | Book 5.1 |
| 11/29 | Halt and ETM are undecidable by reduction to ATM | Sipser pg. 192–194 |
| 12/02 | Rice's Theorem, ALLCFG is undecidable | Book 5.3, Sipser pg. 201 |
| 12/04 | Relationship between recognizable and decidable languages, Complement of ATM and Halt are not recognizable, Diagonalization | Book 5.7, 5.6.2, 5.6.3 |
| 12/06 | Enumerable languages, EQTM | Book 5.5, 5.8 |
| 12/09 | Nondeterministic Turing machines, Time Complexity | |
| 12/11 | Space Complexity, P ⊆NP ⊆PSPACE = NPSPACE ⊆EXPTIME | |
| 12/13 | Computation is everywhere | slides, Game of Life |
| Final on December 20, 14:00~16:00, room 1501 | ||
There will be many small theoretical homework assignments, where you can test your understanding of the course material. You will have about one week to complete one assignment and they can be turned in in either Korean or English.
Do not wait until the last minute to print or download a copy of the homework. Many of the problems will require significant thought. Even if you tend to work right up to the deadline, skimming the problem set early will give you a chance to start thinking about it and to seeking out help if you need it.
If you have trouble solving a homework problem, try doing some easier related problems (for instance from the textbook) first. In any case, if you feel lost, please come and speak with the TAs or the instructor during their office hours.
Homeworks must be submitted on paper in the homework box number 396, next to room 403 in the new IT Building (N1).