CSIE 3110: Formal languages and automata theory

       

Instructor

  • Name: Tony Tan
  • Room: CSIE 516
  • Office hour: By appointment via email
  • Email: tonytan@csie.ntu.edu.tw
  • Personal website

Venue and time

  • Time: Tuesday and Friday, 10:20-13:00
  • There will be around 15 minute break in the middle of each lesson
  • Room: CSIE 102

Teaching assistants

  • 鄭士驤 (Cheng Shih Hsiang), r08922047@ntu.edu.tw, office hour: XXX.
  • 林廷衛 (Lin Tingwei), r08922089@ntu.edu.tw, office hour: XXX.
  • If needed, you may try to arrange another time slot with the TA directly.

Recommended textbooks

  • Introduction to the Theory of Computation by M. Sipser.
  • Introduction to Automata Theory, Languages, and Computation by J. Hopcroft and J. Ullman, 1st edition.

Administrations

  • All notes and homeworks (in both pdf and tex files) will be posted here.
  • To compile the tex file, you will need this file: mysty.sty
  • There will be four homeworks, each weighs 10%.
  • Midterm and final exams weigh 30% each.
  • The instructions on homework submissions will be provided in each homework.

Schedule (tentative)

Part Week Dates Lesson Remark
A I 10 and 13 Sep. Lesson 1. Preliminaries: tex, pdf --
B II 17 and 20 Sep. Lesson 2. Finite state automata: tex, pdf --
III 24 and 27 Sep. Lesson 3. Pumping lemma and regular expressions: tex, pdf --
IV 1 and 4 Oct. Lesson 4. Review week --
C V 8 and 11 Oct. Lesson 5. Context-free languages HW 1 due.
VI 15 and 18 Oct. Lesson 6. Push-down automata --
VII 22 and 25 Oct. Lesson 7. Review week --
VIII 29 Oct. and 1 Nov. Reading week HW 2 due.
IX 5 Nov. Midterm exam: Tuesday evening. --
D X 12 and 15 Nov. Lesson 8. Turing machines and decidable languages --
XI 19 and 22 Nov. Lesson 9. Universal Turing machine, halting problem and reducibility --
XII 26 and 29 Nov. Lesson 10. More on reducibility --
XIII 3 and 6 Dec. Lesson 11. Review week --
E XIV 10 and 13 Dec. Lesson 12. Time and space complexity HW 3 due.
XV 17 and 20 Dec. Lesson 13. NP- and PSPACE-complete languages --
XVI 24 and 27 Dec. Lesson 14. Review week --
XVII 31 Dec. and 3 Jan. Reading week HW 4 due.
XVIII 7 Jan. Final exam: Tuesday evening --