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 104 (class 2) and CSIE 102 (class 1)

Teaching assistants

  • TA mailing list: automata@csie.ntu.edu.tw.
  • If there is an issue that does not need a specific TA to settle, please write to TA mailing list above.
  • 鄭士驤 (Cheng Shih Hsiang), r08922047@ntu.edu.tw, r08922047@csie.ntu.edu.tw, TA hour: Wednesday, 13:00-14:00, room 217.
  • 林廷衛 (Lin Tingwei), r08922089@ntu.edu.tw, r08922089@csie.ntu.edu.tw, TA hour: Monday, 16:00-17:00, room 401.
  • 黃世瑋 (Huang Shiwei), r07944035@ntu.edu.tw, r07944035@csie.ntu.edu.tw, TA hour: Wednesday, 16:00-17:00, room 401.
  • 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)

Week Dates Lesson Remark
Part 0: Preliminaries (tex, pdf)
I 10 and 13 Sep. Lesson 0. Preliminaries --
Part 1: Regular languages (tex, pdf)
II 17 and 20 Sep. Lesson 1.a. Finite state automata --
III 24 and 27 Sep. Lesson 1.b. Pumping lemma and regular expressions Sample solution HW 1: tex, pdf
IV 1 and 4 Oct. Lesson 1.c. Review --
Part 2: Context-free languages (tex, pdf)
V 8 and 11 Oct.
Lesson 2.a. Context-free grammars and pumping lemma
Note: Due to public holiday, the Friday class is moved to Tuesday, 8 Oct., 18:00-20:30.
--
VI 15 and 18 Oct. Lesson 2.b. Push-down automata (for class 2 on Tuesday) Sample solution HW 2: tex, pdf
VII 22 and 25 Oct. Lesson 2.b. Push-down automata (for class 1 on Friday) --
VIII 29 Oct. and 1 Nov. Lesson 2.c. Review --
Reading week and midterm exam
IX 5 and 8 Nov. Reading week --
X 12 Nov. Midterm exam: Tuesday, 12 November, 18:30--20:30, room: 101, 102, 103, 104. --
Part 3: Decidable and undecidable languages (tex, pdf)
XI 19 and 22 Nov. Lesson 3.a. Turing machines and decidable languages --
XII 26 and 29 Nov. Lesson 3.b. Variants of Turing machines --
XIII 3 and 6 Dec. Lesson 3.c. Universal Turing machines and halting problems Sample solution HW 3: tex, pdf
XIV 10 and 13 Dec. Lesson 3.d. Reducibility --
Part 4: Basic complexity theory (tex, pdf)
XV 17 and 20 Dec. Lesson 4.a. Basic complexity classes Sample solution HW 4: tex, pdf
XVI 24 and 27 Dec. Lesson 4.b. NP-complete languages --
Reading week and final exam
XVII 31 Dec. and 3 Jan. Reading week --
XVIII 7 Jan. Final exam: Tuesday, 7 January, 19:00--21:00, room: 101, 102, 103, 104. --