## Announcements

- Grading for the course:

- Homeworks: 35%
- Midterm Exam: 25%
- Final Exam: 40%
- Important Dates:
- Jan 9, 2006: First day of class
- Apr 7, 2006: Last day of class
- Midterm Exam: Mon, Mar 6, 2006
- Final Exam: 8:30am-11:30am, Apr 10, 2006, Room: AQ 5006
- Wed, Oct 12, 2005: Course web page created

## Assignments

Note that all homeworks are due in class on the due date.- Homework #1
- Homework #2
- Homework #3
- Homework #4
- Homework #5
- Homework #6
- Homework #7
- Homework #8
- Homework #9

**Important note on assignment submission and development**: Do not
collaborate on solving the homework. Do not discuss the solutions of the
homework with others outside class. Please bring any questions you
might have to class for discussion.

## Textbook and References

- Textbook:
- Introduction to the Theory of Computation, Michael Sipser, Thompson Course Technology, 2006
- Reference Textbooks:

- Introduction to Automata
Theory, Languages, and Computation: 2/e, John Hopcroft,
Rajeev Motwani and Jeffrey Ullman, Addison-Wesley, 2001

- An Introduction to Formal Languages and Automata, Peter Linz, Jones and Bartlett, 2000

Thanks to Tugkan Batu for his homeworks, exams and their solutions from his MACM 300 course materials. And thanks to Chung-hye Han for notes created from Sipser, and additional homework ideas. We will follow Sipser's textbook fairly closely for this course.

## Syllabus and Readings

- Preliminaries: sets, proof methods
*Reading*: Chp 0, Sipser*Notes*: Notes #1- Finite-state automata, Regular languages
*Reading*: Chp 1, Sipser*Notes*: Notes #2*Notes*: Notes #3*Notes*: Notes #4*Notes*: Notes #5- Regular expressions and regular languages
- Finite-state automata: deterministic and non-deterministic automata
- Pumping lemma for regular languages, closure properties
- Minimizing the size of finite-state automata
- Context-free grammars and context-free languages
*Reading*: Chp 2, Sipser*Notes*: Notes #6*Notes*: Notes #7*Notes*: Notes #8- Left/right-linear context-free grammars
- Normal forms for context-free grammars, the hardest context-free language
- Ambiguity and parsing, deterministic context-free languages
- Pumping lemma for context-free languages, closure properties

- Turing Machines, undecidable problems
*Notes*: Notes #9- Alternative models of computation
- Hierarchy of languages and automata
- Applications (covered briefly with each topic above):
- compilers,
- structured databases,
- natural language processing,
- program verification,
- applications of automata theory to logic

## Course Expectations and Policies

- Students are expected to attend all classes: announcements about assigned readings, homeworks and exams will be made available at the start of each class. Such announcements may not be made on this web page, so don't rely on information here instead of attending class.
- The final grade will be assigned based on the percentage split between the requirements (given above in the Announcements section). The grade will be based on a percentage cutoff, e.g. above 94% overall might be an A+. The actual cutoffs will be determined based on my estimate of the course difficulty at the end of the semester.
- Late assignments will be graded as follows: marks earned for assignments submitted after the due date and time will be multiplied by a 0.8 penalty (even if it was late on the same day as the due date). Submissions two days late will get a penalty of 0.6 * grade, and so on until the penalty reaches 0.2 * grade (Sat, Sun and holidays are included). Any submission identical to a solution key will get zero marks.
- If you must miss an exam because of illness, you are required to contact me prior to the exam either by email or a message in my mailbox. A valid note from a medical doctor is required specifying date of absence and reason. If you miss an exam due to valid medical reasons you will be graded on your performance on the rest of the course. Make up exams will not be given under any circumstances.
- Email policy: Use the prefix "macm-300: " on all your messages. If you do not include the prefix, then the mail might go unanswered. Do not send general questions about the class or the material to me directly. Instead use the class mailing list to post your question.
- For personal advising come during my office hours (posted above).
- Copying on assignments or exams will be taken very seriously. If you are caught cheating on an assignment or an exam you will be hauled off for disciplinary action. There will be no assignments to be solved as a group. Despite this, students often meet to discuss the assignments. You have to be very careful that you do not take any notes or copy during these meetings.
- For more on academic dishonesty read the University code of academic honesty.
- I will give partial credit on exams. If you provide an incorrect answer but your work shows some understanding you will get partial credit, but if you have the correct answer, and your work shows a misunderstanding of the course material you will lose marks.