Formal Languages and Automata (CS322)

Fall Semester 2013

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:

Course information

Otfried Cheong. Office: E3-1 3434, Phone: 3542.
Teaching assistants

김용곤, 조유정, 연주영.


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.

Grading policy

The final grade will be composed as follows (small changes reserved):

  • Homeworks (20%), Midterm exam (30%), Final exam (40%), Attendance (10%).

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

Head-banging sessions

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:

  • Monday, 3pm, in room 111.
  • Monday, 7pm, in room 112.
  • Wednesday, 3pm, in room 111.
  • Friday, 3pm, in room 111.

The current assignment of students to the four head-banging sessions are here.

Bulletin boards

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.

Textbook and other references

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:

  • Introduction to the Theory of Computation, Michael Sipser, Second International Edition, Course Technology 2006.
    Check out its errata page, which contains a few substantive (as opposed to stylistic) errors.
  • Introduction to Automata Theory, Languages, and Computation, by Hopcroft, Ullman, and Motwani, 3rd edition, Addison-Wesley, 2003.
  • The 1979 classic version of the Hopcroft and Ullman textbook;
  • Elements of the Theory of Computation (2nd. ed.) Harry R. Lewis, Christos H. Papadimitriou, Prentice-Hall, August 1997.

Course progress

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

Homework problems

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).