|
Instructor: 顏嗣鈞
E-mail: yen(_at_)cc.ee.ntu.edu.tw
Time:
9:10-12:00 AM,
Monday
Place: Room
BL-114
Office phone:
(02) 3366 3700 ext 123
Office hours:
by appointment
TA:
蕭東榕
hyttmdark@yahoo.com.tw
Announcements:
-
期中考、期末考及作業成績登錄;
星期一(1/21)早上10:00 - 12:00 可至電機二館122室系主任辦公室看考卷
(期末考解答)
-
Final exam
will be held
on January 7 (Monday) 9:10 - 12:00 AM.
-
期中考及作業成績登錄
-
Final Exam covers Chap. 6 (pushdown automata),
Chap. 7 (properties of CFLs), Chap. 8 (Intro. to Turing machines), Chap.
9 (undecidability), and materials discussed in class including basic
recursive function theory, basic complexity theory (time/space
hierarchies, P vs. NP) ... etc.
-
Sample
final exams (2011,
2010,
2009,
2008,
2007,
2006,
2005,
2004,
2001,
1996,
199? )
-
Homework #3 (Solution):
due Dec. 22 (Saturday)
-
Midterm Solutions
-
Homework #2 (Solution):
due Nov. 14 (Wednesday)
-
Midterm exam will be held
on Nov. 12 (Monday) 9:10 - 12:00 AM.
-
Sample midterm exams
1996,
2001,
2002,
2004,
2005 (2005 Solutions:
1,
2,
3),
2006;
2007;
2008;
2009,
2010,
2011
-
Homework # 1 (Solution):
due Oct. 15 (Monday)
-
Classes cancelled on Oct. 29.
-
Invited talk on "Vaucanson:
a finite state machine manipulation platform"
by Prof. Sylvain Lombardy (Université
de Bordeaux, France), 10:30
-- 11:30 AM, Wednesday Oct. 31, Room 124, EE Building #2
Class Notes:
(Access restricted)
This course provides a rigorous,
graduate level introduction to Automata theory, Formal languages, and
Complexity. Topics to be covered will include:
|
Topics
|
| |
Chapter 0 |
Introduction |
0.pdf |
|
|
Chapter 1 |
The Methods and the Machines |
-
deterministic vs.
nondeterministic FA,
-
one-way vs. two-way FA,
-
minimization,
-
pumping lemma for regular sets,
-
closure properties,
-
Myhill-Nerode Theorem,
...
|
1.pdf
2.pdf
|
|
Chapter 2 |
Finite Automata |
|
Chapter 3 |
Regular Expressions and
Languages |
|
Chapter 4 |
Properties of Regular
Languages |
|
Chapter 5 |
Context-free Grammars and
Languages |
- deterministic vs.
nondeterministic PDA,
- one-way vs. two-way PDA,
- reversal bounded PDA,
- linear grammars,
- counter machines,
- pumping lemma for CFLs,
- Chomsky normal form,
- Greibach normal form,
- closure properties,
...
|
3.pdf
4.pdf
5.pdf
|
|
Chapter 6 |
Pushdown Automata |
|
Chapter 7 |
Properties of Context-free
Languages |
|
Chapter 8 |
Introduction to Turing
Machines |
- variants of Turing
machines,
- halting problem,
- undecidability,
- Post correspondence
problem,
- valid and invalid
computations of TMs,
- Basic recursive function
theory, ...
|
6.pdf
7.pdf
8.pdf
9.pdf
|
|
Chapter 9 |
Undecidability |
|
Chapter 10 |
Intractable Problems |
- various
resource bounded complexity classes, including NLOGSPACE, P, NP, PSPACE,
EXPTIME, and many more,
-
reducibility,
-
completeness, ...
|
10.pdf
11.pdf
|
|
Chapter 11 |
Additional Classes of Problems |
|
|
|
Supplementary Materials |
- Weighted automata
- Tree automata,
- Omega automata,
- Probabilistic automata, ...
|
|
|
