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: Monday, 10:20-13:00
  • There will be around 15 minute break in the middle of each lesson
  • Room: CSIE 104

Teaching assistants

  • Liu Han Sheng (b04902012@ntu.edu.tw), office hour: Friday, 13:00--14:00.
  • Ma Yanger (b04902032@ntu.edu.tw), office hour: Wednesday, 13:00--14:00.
  • 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.

Schedule (tentative)

Part Week Dates Lesson Remark
A I 10 Sep. Lesson 1. Preliminaries --
B II 17 Sep. Lesson 2. Deterministic finite state automata --
III 24 Sep. Lesson 3. Nondeterministic finite state automata --
IV 1 Oct. Lesson 4. Regular expressions --
C V 8 Oct. Lesson 5. Context-free languages --
VI 15 Oct. Lesson 6. Push-down automata HW 1 due. HW 2 out.
VII 22 Oct. Lesson 7. CFG = PDA --
VIII 29 Oct. Reading week --
IX 5 Nov. Midterm exam. HW 2 due.
D X 12 Nov. Lesson 8. Turing machines and decidable languages --
XI 19 Nov. Lesson 9. Variants of Turing machines --
XII 26 Nov. Lesson 10. Universal Turing machines and Halting problem --
XIII 3 Dec. Lesson 11. Reducibility, part I HW 3 out.
XIV 10 Dec. Lesson 12. Reducibility, part II --
E XV 17 Dec. Lesson 13. Time and space complexity --
XVI 24 Dec. Lesson 14. NP-complete and PSPACE-complete languages --
XVII 31 Dec. Reading week HW 3 due.
XVIII 7 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 in the indicated week.
  • Their due dates are also always on Mondays at the end of the class in the indicated week.
  • 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.