CSIE 3110: Formal languages and automata theory
- Name: Tony Tan
- Room: CSIE 516
- Office hour: By appointment via email
- Email: firstname.lastname@example.org
- 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
- 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: email@example.com
- Notes and homework can be found in the latest website:
||13 and 15 Sep.
||Lesson 1. Preliminaries
|| HW 1 out.
||Lesson 2. Deterministic finite state automata
||HW 1 due.
||27 and 29 Sep.
Nondeterministic finite state automata
||HW 2 out.
||4 and 6 Oct.
||Lesson 4. Regular expressions
||11 and 13 Oct.
||Lesson 5. Context-free languages
||18 and 20 Oct.
||Lesson 6. Pumping lemma and push-down automata
||HW 2 due. HW 3 out.
||25 and 27 Oct.
||Lesson 7. CFG = PDA
||1 and 3 Nov.
||HW 3 due.
||15 and 17 Nov.
||Lesson 8. Turing machines and decidable languages
||22 and 24 Nov.
||Lesson 9. Variants of Turing machines
||HW 4 out.
||29 Nov. and 1 Dec.
||Note: There is no lecture this week due to
an overseas assignment from the EECS College.
||6 and 8 Dec.
||Lesson 10. Universal Turing machines and Halting problem
||13 and 15 Dec.
||Lesson 11. Reducibility
||20 and 22 Dec.
||Lesson 12. Time and space complexity
||HW 4 due. HW 5 out.
||27 and 29 Dec.
||Lesson 13. NP-complete problems
||3 and 5 Jan.
||HW 5 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 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.