Electrical Engineering
 
Welcome Biography Research Teaching Publications Awards
Lab Professional Activities Research Projects Links

 計算理論 Theory of Computation (Spring 2021)

Instructor: 顏嗣鈞
E-mail:  hcyen(_at_)ntu.edu.tw

Time:  9:10-12:00 AM, Tuesday

Place: Room BL-112

Office phone: (02) 3366 3581

Office hours: by appointment

TA:  王璲  博理館606室      

     (02) 33663700 ext 6606 

        D07921012@ntu.edu.tw    


Announcements:


Class Notes: ( Courtesy of Prof. Bow-Yaw Wang of Academia Sinica for some of the slides)

 

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

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
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 (updated)

Supplementary Materials

  • Weighted automata
  • Tree automata,
  • Omega automata,
  • Probabilistic automata, ...

 

 

 

Textbook:

  • Introduction to the Theory of Computation,  Michael Sipser, (3rd Ed. Thomson) 開發圖書


Grading:  

  • Homework/Project: 20%

  • Midterm exam: 40%

  • Final exam:  40% 

 

 

.