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

 計算理論 Theory of Computation

Fall 2015

 

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

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

Place: Room BL-114

Office phone: (02) 3366 3581

Office hours: by appointment

TA:  顏玓德  博理館606室;

     bottle1116(_at_)hotmail.com

     (02) 33663700 ext 6606     


Announcements:

 


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,

  • one-way vs. two-way FA,

  • minimization,

  • pumping lemma for regular sets,

  • closure 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,  
  • Post correspondence problem,
  • valid and invalid computations of TMs

*3.pdf

*4.pdf

Chapter 4 Decidability
Chapter 5 Reducibility
  • Reductions
  • Undecidability proof
  • Basic recursive function theory, ...
*5.pdf

5a.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

 

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% 

 

 

.