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
- 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: email@example.com
- Li Yu Sheng (firstname.lastname@example.org), office hour: Monday, 1:10--2:10, red sofa in basement.
- Liu Han Sheng (email@example.com), 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.
||Lesson 1. Preliminaries
||Lesson 2. Deterministic finite state automata
||Lesson 3. Nondeterministic finite state automata
||HW 1 out.
||Lesson 4. Regular expressions
||Lesson 5. Context-free languages
||Lesson 6. Pumping lemma and push-down automata
||HW 1 due. HW 2 out.
||Lesson 7. CFG = PDA
||HW 2 due.
||Lesson 8. Turing machines and decidable languages
||Lesson 9. Variants of Turing machines
||Lesson 10. Universal Turing machines and Halting problem
||HW 3 out.
||Lesson 11. Reducibility
||Lesson 12. Time and space complexity
||Lesson 13. NP-complete problems
||Lesson 14. NLog- and PSPACE-complete problems
||HW 3 due. HW 4 out.
||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.