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: Monday, 10:20-13:00
- There will be around 15 minute break in the middle of each lesson
- Room: CSIE 104
- Liu Han Sheng (email@example.com), office hour: Friday, 13:00--14:00.
- Ma Yanger (firstname.lastname@example.org), office hour: Wednesday, 13:00--14:00.
- If needed, you may try to arrange another time slot with the TA directly.
- Introduction to the Theory of Computation by M. Sipser.
- Introduction to Automata Theory, Languages, and Computation by J. Hopcroft and J. Ullman, 1st edition.
||Lesson 1. Preliminaries
||Lesson 2. Deterministic finite state automata
||Lesson 3. Nondeterministic finite state automata
||Lesson 4. Regular expressions
||Lesson 5. Context-free languages
||Lesson 6. 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
||Lesson 11. Reducibility, part I
||HW 3 out.
||Lesson 12. Reducibility, part II
||Lesson 13. Time and space complexity
||Lesson 14. NP-complete and PSPACE-complete languages
||HW 3 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 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.