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

  • Class 02: Tuesday, 09:10-12:00
  • Class 01: Thursday, 09:10-12:00
  • There will be around 15 minute break in the middle of each lesson
  • Room: CSIE 102

Administration

  • Please check this website regularly.
  • All the course notes and homework will be posted here.
  • All the announcements will also be posted here, as well as in the bulletin of this course in CEIBA.
  • This document (2016a-aut-admin.pdf) contains more information about the course.
  • If you want to send me email, please use: tonytan@csie.ntu.edu.tw
  • Notes and homework can be found in the latest website: https://www.csie.ntu.edu.tw/~tonytan/teaching/2017a-aut/2017a-aut.html

Schedule (tentative)

Part Week Dates Lesson Remark
A I 13 and 15 Sep. Lesson 1. Preliminaries HW 1 out.
B II 22 Sep. Lesson 2. Deterministic finite state automata HW 1 due.
III 27 and 29 Sep. Lesson 3. Nondeterministic finite state automata HW 2 out.
IV 4 and 6 Oct. Lesson 4. Regular expressions --
C V 11 and 13 Oct. Lesson 5. Context-free languages --
VI 18 and 20 Oct. Lesson 6. Pumping lemma and push-down automata HW 2 due. HW 3 out.
VII 25 and 27 Oct. Lesson 7. CFG = PDA --
VIII 1 and 3 Nov. Reading week HW 3 due.
IX 8 Nov. Midterm exam --
D X 15 and 17 Nov. Lesson 8. Turing machines and decidable languages --
XI 22 and 24 Nov. Lesson 9. Variants of Turing machines HW 4 out.
XII 29 Nov. and 1 Dec. Note: There is no lecture this week due to an overseas assignment from the EECS College. --
XIII 6 and 8 Dec. Lesson 10. Universal Turing machines and Halting problem --
XIV 13 and 15 Dec. Lesson 11. Reducibility --
E XV 20 and 22 Dec. Lesson 12. Time and space complexity HW 4 due. HW 5 out.
XVI 27 and 29 Dec. Lesson 13. NP-complete problems --
XVII 3 and 5 Jan. Reading week HW 5 due.
XVIII 10 Jan. Final exam --

Notes on homeworks

  • You should write down your class number, your student number and your name in your homework solution.
  • Homeworks will be posted here on Mondays at 17:00 in the indicated week.
  • Their due dates are also always on Mondays at 17:00 in the indicated week, except Homeworks 3 and 5 which are due on Friday, 17:00, respectively.
  • You can submit your homework earlier than the due date by slipping it under the door of my office.
  • Homework can be handwritten or typewritten. If it is handwritten, the writing must be legible.
  • The tidiness of your homework contributes to your grade.
  • Discussions/collaborations are allowed, but make sure that you acknowledge that you do your homeworks in collaboration and that you understand and write down your own solutions.
  • Points will be deducted if you don't understand your own solutions.