NCTU CS: Undergraduate Formal Languages (Spring 2006)

Course Information

Instructor

Wuu Yang, <wuuyang@cis.nctu.edu.tw>, EC332B, 03-5712121 ext. 56614.

Teaching Assistants

滕元翔, 分機 56655, e-mail:gis93806@cis.nctu.edu.tw. or all graduate students at 分機 56649.

Lectures

2B5EF, ED117. February 20-June 19, 2006.

Course URL

http://www.cis.nctu.edu.tw/~wuuyang/Lecture/lecture.formal.html

Prerequisites

programming in a conventional language (such as C, C++, or Pascal).

Course Description

This course --Formal Languages-- is a foundation of the theoretic part of the computer science. We will study the four kinds of formal languages and their relation to computability and complexity theory.

1. Introduction to The Theory of Computation
2. Finite Automata
3. Regular Languages and Regular Grammars
4. Properties of Regular Languages
5. Context-Free Languages
6. Simplification of Context-Free Grammars
7. Pushdown Automata
8. Properties of Context-Free Languages
9. Turing Machines
10. Other Models of Turing Machines
11. A Hierarchy of Formal Languages and Automata
12. Limits of Algorithmic Computation
13. Other Models of Computation
14. An Introduction to Computational Complexity

Textbook

Peter Linz, An Introduction to Formal Languages and Automata, 4th ed., Jones and Bartlett Publisher, 2006.

(reference only) A.V. Aho, R. Sethi, and J.D. Ullman, Compilers, Principles, Techniques, and Tools, Addison-Wesley, 1985.

(reference only) M.R. Garey and D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979.

Grading

There will be two exams (40% each), several written homeworks (15%), and classroom participation (5%).

Midterm exam will be on April 21, 2006, Friday.

Final exam will be on June 23, 2006, Friday.

Class material

Class material: chapter 1; chapter 2; chapter 3; chapter 4; chapter 5; chapter 6; chapter 7; chapter 8; chapter 9; chapter 10; chapter 11; chapter 12; chapter 13; chapter 13-1 (Recursive functions); , chapter 14.
Church-Turing Thesis
Timed automata: Timed model checking of security protocols
A Turing-machine package in Java

Homework

First homework: finite automaton for URL. Due March 17, 2006, Friday, beginning of class.
Second homework: finite automaton for URL. Due March 24, 2006, Friday, beginning of class.
Third homework: finite automata. Due March 31, 2006, Friday, beginning of class.
4th HOMEWORK: chap 7. 7-1 No. 3; 7-2 Nos.5, 6; 7-3 No. 8. DUE 5/12, 2006.
5th HOMEWORK: chap 8. p. 220 Nos. 12, 16, 17. Due 5/19, 2006.
6th HOMEWORK: chap 9. p. 236 Nos. 5, 7(f), 8, 9, 11(c); p.212 3(c). Due 6/6, 2006.

Local On-Line Information

Information on the Net

aaaaa

Wuu Yang, <wuuyang@cis.nctu.edu.tw>, EC332B, 03-5712121 ext. 56614.