CSIE 3110: Formal languages and automata theory



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

Venue and time

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


  • 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.
  • If you want to send me email, please use: tonytan@csie.ntu.edu.tw

Teaching assistants

  • Li Yu Sheng (b03902086@ntu.edu.tw), office hour: Monday, 1:10--2:10, red sofa in basement.
  • Liu Han Sheng (b04902012@ntu.edu.tw), office hour: Thursday, 1:30--3:00, red sofa in basement.
  • If needed, you may try to arrange another time slot with the TA directly.

Schedule (tentative)

Part Week Dates Lesson Remark
A I 14 Sep. Lesson 1. Preliminaries --
B II 21 Sep. Lesson 2. Deterministic finite state automata --
III 28 Sep. Lesson 3. Nondeterministic finite state automata HW 1 out.
IV 5 Oct. Lesson 4. Regular expressions --
C V 12 Oct. Lesson 5. Context-free languages --
VI 19 Oct. Lesson 6. Pumping lemma and push-down automata HW 1 due. HW 2 out.
VII 26 Oct. Lesson 7. CFG = PDA --
VIII 2 Nov. Reading week --
IX 9 Nov. Midterm exam HW 2 due.
D X 16 Nov. Lesson 8. Turing machines and decidable languages --
XI 23 Nov. Lesson 9. Variants of Turing machines --
XII 30 Nov. Lesson 10. Universal Turing machines and Halting problem HW 3 out.
XIII 7 Dec. Lesson 11. Reducibility --
E XIV 14 Dec. Lesson 12. Time and space complexity --
XV 21 Dec. Lesson 13. NP-complete problems --
XVI 28 Dec. Lesson 14. NLog- and PSPACE-complete problems HW 3 due. HW 4 out.
XVII 4 Jan. Reading week --
XVIII 11 Jan. Final exam HW 4 due.

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 Thurdays in the indicated week.
  • Their due dates are also always on Thursdays at the end of the class in the indicated week.
  • You can submit your homework earlier than usualthe 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.