Instructor: | Gianfranco Ciardo (ciardo@iastate.edu) |
Lectures: | Mon/Wed/Fri 9:00am - 9:50am, Room: MOL-BIO 1414 |
Recitations: | Thu 8:00am - 8:50am, Room: PEARSON 1105
Wed 2:10pm - 3:00pm, Room: GILMAN 1051 Thu 3:10pm - 4:00pm, Room: GILMAN 2109 |
Textbook: | Introduction to Automata Theory, Languages, and Computation (3rd Edition)
by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman (Addison Wesley) Important note: An international paperback version of the textbook is available, at a much lower price than the harcopy. However, reviews on Amazon.com state that the two editions contain different exercises at the end of each chapter. I do not assign exercises from the textbook, so this may not be an issue, but you should be aware of this fact. |
Instructor office hours: | Thu 2:10pm-3:00pm, Room: Atanasoff 226 |
TAs: | Andrei Nikolai Migunov (amigunov@iastate.edu)
Kiana Mousavi Hanjani (kmousavi@iastate.edu) Seyedehzahra Hosseini (hosseini@iastate.edu) |
TA office hours: | Tue 1:00pm-2:00pm, Room PEARSON 0145 Wed 12:00pm-1:00pm, Room PEARSON 0145 Thu 10:00am-11:00am, Room PEARSON 0145 Thu 2:00pm-3:00pm, Room PEARSON 0145 Fri 1:00pm-2:00pm, Room PEARSON 0145 Fri 3:00pm-4:00pm, Room: PEARSON 0145 |
Final examination: | Fri Dec 15, 7:30am - 9:30am (TENTATIVE) |
Prerequisites: | Minimum of C- in ComS 228, Math 166, and in ComS 230 or CprE 310; ENGL 250 |
Catalog description: | Models of computation: finite state automata, pushdown automata and Turing machines. Study of grammars and their relation to automata. Limits of digital computation, unsolvability and Church-Turing thesis. Chomsky hierarchy and relations between classes of languages. |
The contents of this course are fundamental to computer science. The course is typically considered challenging, but also highly rewarding. For the homework exercises, you must think both logically and creatively. The best way to do well in this course is to attack each exercise set as soon as it is handed out. After you consider various approaches to an exercise for a while, you might want to put it down and come back to it a day or two later. The right solution might just jump at you. Above all, realize that the best way to fail this course is to start working on your homeworks the night before they are due!
After briefly reviewing basic background and introductory notions, the rest of the course can be divided into three main portions, each of them requiring approximately one month: regular languages, context-free languages, and Turing machines.
You are required to attend, follow, and actively participate in all lectures and discussions. Lectures, discussions, and exams start at the stated time. Avoid being late coming to class, as this is very disruptive to the instructor and to your fellow students.
You are requested to refrain from using electronic devices (laptops, cell phones, music players, etc.) during lectures and exams. If, for some compelling reason, you need to be on call, be sure to put your cell phone in silent mode, and excuse yourself from the class if you need to take a call.
Analogously, when you come see me or a TA, please turn your cell phone off, and be sure to bring paper and pen to take notes.
The best way to reach a TA is to go to recitations or to their office hours.
The second best way is to send them an email.
The best way to reach me is to come during office hours
(I will be there, barring emergencies).
The second best way is to send me an email
(I check it quite frequently).
The third best way is to try to see if I am available in my office
(I am almost always on campus during the work week, but I am often in meetings).
Weekly homework sets will be assigned (usually on Fridays) and will be due every Friday night at 11:59pm. (this includes the last Friday of classes, during Dead Week). Overall, they account for 40% of your grade. Both posting of the assignments and turn-in will be through Canvas.
One of the goals of this course is to learn how to write high-quality technical prose. To improve the terseness and readability of your homeworks, I am requiring you to typeset your homeworks in LaTeX, which is freely available. I provide examples of LaTeX files for you to learn how to format particular equations. Pictures, diagrams, and graphs can be drawn using tgif or any other drawing tool that can generate "eps" or "pdf" files, which can then be included into LaTeX. You can also create beautiful pictures directly in LaTeX using the TikZ package, but it does have a learning curve and it is not a WYSIWYG editor, so this approach requires more effort.
Students in the class are allowed to discuss the homework problems among themselves and with me and the TAs, but not with anybody else. An empty hand policy must be observed when you meet with other classmates: you are free to discuss any aspect of the homework, but you must leave the meeting without any record (on paper, magnetic tape, digital storage, or other means) of these discussions. This is because the actual writing of the detailed homework answers must be an individual activity, so that each student can receive an individual grade for each homework.
Unless stated otherwise, sharing of information in permanent format (such as accessing someone else's files, hardcopy outputs, or handwritten notes), will be considered cheating. If you have even the slightest doubt about whether a certain activity is admissible, ask me before you do it!
You are of course allowed, actually encouraged, to consult other reference material in addition to your textbook and class notes. However, if you used this reference to derive the answer to an exercise, you should give it proper credit in your write-up. In no case you should copy verbatim from a reference without proper attribution, as this is plagiarism.
It is a bad idea to search for homework solutions on the web: you might find the answer, but you will have not learned how to come up with the answer by yourself.
I do not accept late homeworks except for justifiable reasons, such as an illness with a doctor's written note.
Each homework consists of one or more exercises. Each exercises carries a weight (usually 10, 25, 50, 75, or 100 points) and students are required to solve all exercises. The grade on each exercise is a number between 0 and its weight. The overall grade for the homeworks as a whole, on a scale of 0 to 1, is determined by summing the grades of all the exercises and dividing the result by the sum of all the weights. Occasionally there may be extra-credit exercises, which you might attempt in order to boost your grade (their grade is added to the sum of the grades but their weight is not added to the sum of weights).
While I may choose to give you partial credit on an exercise, almost always an answer is either "right" (perhaps with minor notational errors or problems that can be easily fixed) or "wrong" (completely incorrect because of some fundamental flaw in your reasoning). Thus, the grade you receive on each individual exercise is usually either close to the maximum or close to zero. However, there are multiple exercises in a homework set, so the overall grades can, and usually do, span a wide range.
I believe that exams should be administered to test
your understanding of the material, not your memorization skills.
Thus, you can use your textbook and your class notes during in-class exams.
However, you must check with me before consulting any additional references
(and my answer will be negative, usually).
Of course, no laptops, tablets, phones, pagers, or similar devices
can be used for the duration of an exam.
There will be two in-class exams during the course (after completing lectures on regular languages and on context-free languages, respectively), each accounting for 15% of your grade, and a final exam covering the entire course material, accounting for 30% of your grade.
You must do at least somewhat well in these in-class exams in order to pass the course. The exercises in these exams are similar to those in the homeworks; thus, you should be able to gauge how you will do in the in-class exams by your comfort level in solving the homework exercises.
An overall grade of at least 90% results in a final grade A.
An overall grade of at least 80% but less than 90% results in a final grade
B.
An overall grade of at least 70% but less than 80% results in a final grade
C.
An overall grade of at least 60% but less than 70% results in a final grade
D.
An overall grade of less than 60% results in a final grade
F.
I reserve the right to raise the final grade, but not to lower it: if your overall grade is 89%, I might decide to give you an A- or a B+, but if it is 80% you are guaranteed at least a B.
This schedule is not written in stone, I expect that deviations from it will occur over the course of the semester. The dates of the exams, however, will not change.
Week | 1 | Mon | Aug | 21 | Background: set, relation, function, contradiction, induction. |
Wed | Aug | 23 | New concepts: languages, grammars, automata. | ||
Fri | Aug | 25 | Regular expressions. | ||
Week | 2 | Mon | Aug | 28 | Deterministic finite automata (DFA). [HW 0 due] |
Wed | Aug | 30 | Nondeterministic finite automata (NFA). | ||
Fri | Sep | 1 | Equivalence of DFA and NFA. [HW 1 due] | ||
Week | 3 | Mon | Sep | 4 | University holiday |
Wed | Sep | 6 | DFA minimization. | ||
Fri | Sep | 8 | Closure properties of regular languages. [HW 2 due] | ||
Week | 4 | Mon | Sep | 11 | Equivalence or regular expressions and finite automata. |
Wed | Sep | 13 | Pumping lemma for regular languages. | ||
Fri | Sep | 15 | Regular grammars. [HW 3 due] | ||
Week | 5 | Mon | Sep | 18 | BONUS: Decision diagrams |
Wed | Sep | 20 | Review and exercises on regular languages. | ||
Fri | Sep | 22 | Review and exercises on regular languages. [HW 4 due] | ||
Week | 6 | Mon | Sep | 25 | In-class exam on regular languages. Context-free grammars (CFG). |
Wed | Sep | 27 | Context-free grammars (CFG). Derivations. | ||
Fri | Sep | 29 | Parse trees. Ambiguous grammars and languages. [HW 5 due] | ||
Week | 7 | Mon | Oct | 2 | Grammar transformations. |
Wed | Oct | 4 | Chomsky and Greibach normal forms. The CYK algorithm. | ||
Fri | Oct | 6 | Nondeterministic pushdown automata (NPDA). [HW 6 due] | ||
Week | 8 | Mon | Oct | 9 | Equivalence of CFG and NPDA. |
Wed | Oct | 11 | Pumping lemma for context-free languages. | ||
Fri | Oct | 13 | Properties of context-free languages. [HW 7 due] | ||
Week | 9 | Mon | Oct | 16 | Deterministic pushdown automata. |
Wed | Oct | 18 | BONUS: Petri net languages. | ||
Fri | Oct | 20 | Turing machines. [HW 8 due] | ||
Week | 10 | Mon | Oct | 23 | Review and exercises on context-free languages. |
Wed | Oct | 25 | In-class exam on context-free languages. | ||
Fri | Oct | 27 | Turing-decidable languages, Turing-acceptable languages, and Turing-computable functions. [HW 9 due] | ||
Week | 11 | Mon | Oct | 30 | Turing's thesis and Turing machine variants. |
Wed | Nov | 1 | Nondeterministic Turing machines. | ||
Fri | Nov | 3 | A universal Turing machine. [HW 10 due] | ||
Week | 12 | Mon | Nov | 6 | Turing-decidable vs. Turing-acceptable languages. |
Wed | Nov | 8 | The halting problem and its implications. | ||
Fri | Nov | 10 | Unrestricted grammars. [HW 11 due] | ||
Week | 13 | Mon | Nov | 13 | Context-sensitive languages. |
Wed | Nov | 15 | Linear-bounded automata. | ||
Fri | Nov | 17 | Recursive and recursively-enumerable sets. [HW 12 due] | ||
Mon | Nov | 20 | Thanksgiving break. | ||
Wed | Nov | 22 | Thanksgiving break. | ||
Fri | Nov | 24 | Thanksgiving break. | ||
Week | 14 | Mon | Nov | 27 | The Post correspondence problem. |
Wed | Nov | 29 | Undecidable problems for context-free languages. | ||
Fri | Dec | 1 | The language hierarchy. [HW 13 due] | ||
Week | 15 | Mon | Dec | 4 | Review and exercises on Turing-decidable and Turing-acceptable languages. |
Wed | Dec | 6 | Review and exercises on the entire course material. | ||
Fri | Dec | 8 | Review and exercises on the entire course material. [HW 14 due] | ||
Fri | Dec | 15 | In-class final exam (TENTATIVE). |