NCTU CS: Undergraduate Formal Languages (Fall 2010)

Course Information

Instructor

Teaching Assistants

王維綱  bishopgang@gmail.com
 實驗室分機: 54744    實驗室: EC120 .

Lectures

Office Hours

Course URL

Prerequisites

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) M. Sipser, Introduction to the Theory of Computation, 2nd ed., Thomson, 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

Midterm exam will be on November 11, 2010, Thursday.   ANSWERS TO THE MIDTERM EXAM (2010-11-17)

Final exam will be on January 13, 2011, Thursday.

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

Current Homework For Fall 2010. 

ANSWERS TO HOMEWORK 1-7.

ANSWERS TO HOMEWORK 8-10, 2010.11.25.

ANSWER TO HOMEWORK 11, 20101129.

ANSWER TO HOMEWORK 12, 20101206.

ANSWER TO HOMEWORK 13, 20101214.

ANSWER TO HOMEWORK 14, 20101224.

ANSWER TO HOMEWORK 15, 20101224.

ANSWER TO HOMEWORK 16, 20110105.

ANSWER TO HOMEWORK 17, 20110105.

ANSWER TO HOMEWORK 18, 20110105.

• Homework 1: .
• Homework 2: .
• Homework 3 (10/7): p. 62--5, 9; p. 68--1; p.69--5.
• Homework 4 (10/11): slide 3-40, No.5; p. 75, No. 5; p. 76, No. 15.
• Homework 5: (10/14) p. 75, No. 4, 6(b)(d); p. 76, No. 14, 17(b)(d); p. 77, No. 26.
• Homework 6: (10/18) p. 87, No. 4 (b)(d), 8; p. 88, No. 13(b).
• Homework 7: (10/21) p. 96, 2, 5; p. 97, 12, 15.
• Homework 8: (10/>??)

Previous Homework

• Homework 1: (9/29) Prove that the set of all strings over a finite, non-empty vocabulary is countable.
• Homework 2: (10/9) p. 34, No. 6, 9. p. 47, No. 3, 4.
• Homework 3: (10/16) p. 55, No. 7, 13. p. 62, No. 4, 12. p. 69, No. 5.
• Homework 4: (10/23) p. 88, No. 13. p. 89, No. 14. p. 97, No. 13(cde), 15.
• Homework 5: (10/30) p. 109, No. 6. p. 110, No. 17, 20, 21. p. 113, No. 3, 9.
• Homework 6: (11/6) p. 134, No. 9, 11, 15. p. 145, No. 5, 7.
• 　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