參見課程網站 http://ccf.ee.ntu.edu.tw/~yen/courses/TOC-2024.html This course provides a rigorous, graduate level introduction to Automata Theory, Formal Languages, and Complexity. Topics to be covered will include: (1). Finite automata, Regular languages, Regular grammars: Deterministic vs. nondeterministic, one-way vs. two-way finite automata, minimization, pumping lemma for regular sets, closure properties. (2). Pushdown automata, Context-free languages, Context-free grammars: Deterministic vs. nondeterministic, one-way vs. two-way PDAs, reversal bounded PDAs, linear grammars, counter machines, pumping lemma for CFLs, Chomsky normal form, Greibach normal form, closure properties. (3). Linear bounded automata, Context-sensitive languages, Context-sensitive grammars. (4). Turing machines, Recursively enumerable sets, Type 0 grammars: Variants of Turing machines, halting problem, undecidability, Post correspondence problem, valid and invalid computations of TMs. (5). Basic recursive function theory (6). Basic complexity theory: Various resource bounded complexity classes, including NLOGSPACE, P, NP, PSPACE, EXPTIME, and many more. reducibility, completeness. (7). Advanced topics in complexity theory: Approximation algorithms, probabilistic complexity, parallel complexity, Alternation, interactive proof systems, oracle computations.

參見課程網站 http://ccf.ee.ntu.edu.tw/~yen/courses/TOC-2024.html

Homework/Project: 20% Midterm exam: 40% Final exam: 40%

教科書： 教科書: 上課後決定 參考書目：