Instructor: 顏嗣鈞
E-mail: hcyen(_at_)ntu.edu.tw
Time:
9:10-12:00 AM,
Tuesday
Place: Room
BL-11 2
Office phone:
(02) 3366 3581
Office hours:
by appointment
TA:
王璲 博理館606室
(02) 33663700
ext 6606
D07921012@ntu.edu.tw
Announcements:
助教: 6/22 (一) 下午 1:00 - 3:30
地點:
博理館217室
老師:
6/19 (五) 下午 2:30 - 5:00
地點: 計算機中心二樓220
-
Sample final exams (2018, 2017,
2016,2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2001, 1996, 199? )
-
Homework #
4:
(Solution) Due:
June
23, 2020
-
Homework #
3:
(Solution) Due:
June
2, 2020
-
Midterm Solutions
-
Homework #
2:
(Solution)
Due: April
28, 2020
-
Midterm will be held on
April 21 (Tuesday), 9:10 - 12:00.
助教: 4/17 (五) 下午 2:30 - 5:00
地點:
博理館213室
or By Appointment (email to
D07921012@ntu.edu.tw )
老師: 4/20 (一) 下午
3:00 - 5:00 視訊 (Webex
Website)
-
Sample midterm exams 2008;
2009;
2010;
2011;
2012;
2013;
2014;
2015;2016
;
2017;
2018
-
3/31 (二) 由 10:10 AM
開始上課
-
Homework # 1: (Solution) Due: April 14, 2020
Class Notes:
(Courtesy of Prof. Bow-Yaw Wang of
Academia Sinica)
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 and mathematical
notations |
Intro.pdf
0.pdf |
|
|
Chapter 1 |
Regular
Languages |
- deterministic vs.
nondeterministic FA,
- minimization
- pumping lemma for regular
sets,
- closure properties,
- decision properties,
- Myhill-Nerode theorem ...
|
1.pdf
1a.pdf
1b.pdf
1c.pdf |
|
Chapter 2 |
Context-free
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,
...
|
2.pdf
2a.pdf
|
|
Chapter 3 |
The Church-Turing Thesis |
- variants of Turing
machines,
- halting problem,
- undecidability,
- valid and invalid
computations of TMs
|
3.pdf
3a.pdf
|
|
Chapter 4 |
Decidability |
|
Chapter 5 |
Reducibility |
- Reductions
- Undecidability proof
- Post correspondence
problem,
- Basic recursive function
theory, ...
|
4.pdf
5.pdf |
|
Chapters 7-8 |
Complexity Theory |
- various
resource bounded complexity classes, including NLOGSPACE, P, NP, PSPACE,
EXPTIME, and many more,
-
reducibility,
-
completeness, ...
|
6.pdf
7.pdf
8.pdf |
|
Supplementary Materials |
- Weighted automata
- Tree automata,
- Omega automata,
- Probabilistic automata, ...
|
|
|
