ComS 331 --- Theory of Computing --- 3 Credits
Fall 2017

Instructor: Gianfranco Ciardo (
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 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 (
Kiana Mousavi Hanjani (
Seyedehzahra Hosseini (
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.

Attendance and basic etiquette

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.

Homework grading method

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.

In class examinations

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.

Final grade policy

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.

Detailed schedule

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 1MonAug21Background: set, relation, function, contradiction, induction.
WedAug23New concepts: languages, grammars, automata.
FriAug25Regular expressions.
Week 2MonAug28Deterministic finite automata (DFA). [HW 0 due]
WedAug30Nondeterministic finite automata (NFA).
FriSep 1Equivalence of DFA and NFA. [HW 1 due]
Week 3MonSep 4University holiday
WedSep 6DFA minimization.
FriSep 8Closure properties of regular languages. [HW 2 due]
Week 4MonSep11Equivalence or regular expressions and finite automata.
WedSep13Pumping lemma for regular languages.
FriSep15Regular grammars. [HW 3 due]
Week 5MonSep18BONUS: Decision diagrams
WedSep20Review and exercises on regular languages.
FriSep22Review and exercises on regular languages. [HW 4 due]
Week 6MonSep25In-class exam on regular languages. Context-free grammars (CFG).
WedSep27Context-free grammars (CFG). Derivations.
FriSep29Parse trees. Ambiguous grammars and languages. [HW 5 due]
Week 7MonOct 2Grammar transformations.
WedOct 4Chomsky and Greibach normal forms. The CYK algorithm.
FriOct 6Nondeterministic pushdown automata (NPDA). [HW 6 due]
Week 8MonOct 9Equivalence of CFG and NPDA.
WedOct11Pumping lemma for context-free languages.
FriOct13Properties of context-free languages. [HW 7 due]
Week 9MonOct16Deterministic pushdown automata.
WedOct18BONUS: Petri net languages.
FriOct20Turing machines. [HW 8 due]
Week10MonOct23Review and exercises on context-free languages.
WedOct25In-class exam on context-free languages.
FriOct27Turing-decidable languages, Turing-acceptable languages, and Turing-computable functions. [HW 9 due]
Week11MonOct30Turing's thesis and Turing machine variants.
WedNov 1Nondeterministic Turing machines.
FriNov 3A universal Turing machine. [HW 10 due]
Week12MonNov 6Turing-decidable vs. Turing-acceptable languages.
WedNov 8The halting problem and its implications.
FriNov10Unrestricted grammars. [HW 11 due]
Week13MonNov13Context-sensitive languages.
WedNov15Linear-bounded automata.
FriNov17Recursive and recursively-enumerable sets. [HW 12 due]
MonNov20Thanksgiving break.
WedNov22Thanksgiving break.
FriNov24Thanksgiving break.
Week14MonNov27The Post correspondence problem.
WedNov29Undecidable problems for context-free languages.
FriDec 1The language hierarchy. [HW 13 due]
Week15MonDec 4Review and exercises on Turing-decidable and Turing-acceptable languages.
WedDec 6Review and exercises on the entire course material.
FriDec 8Review and exercises on the entire course material. [HW 14 due]
FriDec15In-class final exam (TENTATIVE).

Academic dishonesty

The class will follow Iowa State University's policy on academic dishonesty. Anyone suspected of academic dishonesty will be reported to the Dean of Students Office. See

Disability accommodation

Iowa State University complies with the Americans with Disabilities Act and Sect 504 of the Rehabilitation Act. If you have a disability and anticipate needing accommodations in this course, please contact me to set up a meeting within the first two weeks of the semester or as soon as you become aware of your need. Before meeting with me, you will need to obtain a SAAR form with recommendations for accommodations from the Disability Resources Office, located in Room 1076 on the main floor of the Student Services Building. Their telephone number is 515-294-7220 and their email is Retroactive requests for accommodations will not be honored.

Dead week

This class follows the Iowa State University Dead Week guidelines as outlined in

Harassment and discrimination

Iowa State University strives to maintain our campus as a place of work and study for faculty, staff, and students that is free of all forms of prohibited discrimination and harassment based upon race, ethnicity, sex (including sexual assault), pregnancy, color, religion, national origin, physical or mental disability, age, marital status, sexual orientation, gender identity, genetic information, or status as a U.S. veteran. Any student who has concerns about such behavior should contact me, Student Assistance at 515-294-1020, or email, or the Office of Equal Opportunity and Compliance at 515-294-7612.

Religious accommodation

If an academic requirement conflicts with your religious practices and/or observances, you may request reasonable accommodations. Your request must be in writing, and I will review the request. You may also seek assistance from the Dean of Students Office or the Office of Equal Opportunity and Compliance.

Last updated: August 17, 2017
Report suggestions and problems to