CS 301 Languages and Automata
Fall 2010: (Call no 10647 (class) and 10645 (discussion))
Instructor:
Ajay Kshemkalyani
Email:
first name @ uic.edu
Class meeting times: TR 9:30 - 10:45pm in LC A6
Office Hours (in 915 SEO): T,R 11:00 - 11:50pm
TA: Min Shen
Email: mshen6 @ uic.edu
Recitation section time: F 12:00-12:50pm in SES 238
The recitation section meetings will begin from the third week, i.e., Sept 10.
We may occasionally skip it in some week.
Office Hours (in 932 SEO):
W 3:00-5:00pm; F 10:00-11:00 am and 1:00-2:00pm, phone 996-5941.
-
[Required:]
Sipser, Michael,
Introduction to the Theory of Computation. Course Technology/Cengage Learning, 2nd edition 2006.
- [Suggested Additional book:]
Hopcroft, Motwani, Ullman,
An Introduction to Automata Theory, Languages, and Computation,
3rd edition, Addison Wesley, 2006.
- PDFs of class transparencies.
- Chapter 0, Introduction, added 9/30/10
- Chapter 1, Finite Automata, added 9/30/10
- Chapter 1, Non-regular languages, added 11/04/10 to replace version of 9/30/10
- Chapter 2, Push-Down Automata, added 11/04/10
- Chapter 3, Turing Machines, added 11/04/10
- Chapter 4, Decidable Languages, added 11/18/10
- Chapter 5, Reducability(Initial part), added 11/24/10 (does NOT cover the entire syllabis for the final)
- The Game of Life
- Computability
- Chomsky hierarchy of grammars
- Tiling problem, Halting problem, simplified
- Examples of undecidable problems (Wapedia) or from Wikipedia
Web page:
Please read it regularly.
All announcements will be made here, in addition to tracking the course
progress during the semester.
This course focuses on theoretical principles.
You will not be programming in this course.
This course presents some of the most fundamental results in
theoretical Computer Science.
These results attempt to answer, in a precise mathematical sense, the
following two questions, which are of practical as well as
philosophical interest:
- Can a given problem be solved by computation?
- How efficiently can a given problem be solved by computation?
We focus on problems rather than on specific
algorithms for solving problems.
To answer both questions mathematically, we need to start by formalizing the
notion of "computer" or "machine".
So the course outline breaks naturally into three parts:
- Models of computation (Automata Theory) (Sipser: Chapters 1, 2, 3)
- Finite automata
- Push-down automata
- Turing machines
- What can we compute? (Computability Theory) (Sipser: Chapters 4, 5)
- How efficient can we compute? (Complexity Theory) (Sipser: Chapters 7, 8)
The specific contents we plan to cover are as follows.
- Chapter 0: Introduction, mathematical notation, proof techniques
- Chapter 1: Deterministic finite automata (DFA), nondeterministic finite automata (NFA); RE=NFA, nonregular languages/RE pumping lemma
- Chapter 2: Context-free grammars (CFG), Chomsky normal form, all RL are CFG; Pushdown automata (PDA), Non-CF languages/CFL pumping lemma
- Chapter 3: Turing machines (TMs), TM decidable languages, TM recognizable languages, Equivalence between multitape TMs, Equivalence between nondeterministic TMs and other models, Church-Turing thesis
- Chapter 4: Decidable languages, decidability RL/PDAs/RE; Decidability CFLs/CFGs, Halting problem, counting/diagonalization; Undecidability of the Halting problem, TM unrecognizable languages
- Chapter 5: Computation histories, examples of undecidable languages; TM computable functions, mapping reducibility
- Chapter 7 (we will try to cover some sections from this chapter): Time-complexity, polynomial time (P), languages in P, Strong Church-Turing thesis; Nondeterministic polynomial time (NP), SAT; Polynomial time reductions, NP-completeness, 3SAT versus CLIQUE, Cook-Levin Theorem; Proof Cook-Levin theorem, NP-completeness of SAT and 3SAT, proving NP-completeness; NP-completeness of HAMPATH, SUBSET SUM
- Chapter 8 (we may not have time for this chapter):
Space complexity, Savitch's theorem, PSPACE, PSPACE completeness, TQBF.
- Week 1
- T Aug 24: Overview
- R Aug 26: Overview (proof techniques)
- F Aug 27: No discussion section.
- Week 2
- T Aug 31: Overview completed.
Chapter 1 begun.
- R Sep 2: DFAs, computations. Homework 1 assigned
- F Sep 3: No discussion section.
- Week 3
- T Sep 7: DFAs, Regular languages, closure under regular operations
- R Sep 9: Nondeterminism, NFAs. Homework 2 assigned
- F Sep 10: Homework 1 due by 12 noon
- Week 4
- T Sep 14: NFAs definition, Equivalence between NFAs and DFAs
- R Sep 16: Equivalence between NFAs and DFAs, Closure under regular operations using NFAs. Homework 3 assigned
E-Mail submissions of homeworks are not acceptable.
- F Sep 17: Homework 2 due by 12 noon
- Week 5
- T Sep 21: Regular expressions/grammar, Equivalence between NFA/DFA and regular language/ grammar, Homework 4 assigned
- R Sep 23: Equivalence between NFA/DFA and regular language/ grammar
- F Sep 24: Homework 3 due by 12 noon
- Week 6
- T Sep 28: Pumping lemma for regular languages, non-regular languages, Homework 5 assigned
- R Sep 30: non-regular languages, more pumping lemma proofs
- F Oct 1: Homework 4 due by 12 noon
- Week 7
- T Oct 5: Midterm 1: Chapters 0, 1
- R Oct 7: Chapter 2 begun. Context-free grammars, context-free languages, parse trees, Homework 6 assigned
- F Oct 8: Homework 5 due by 12 noon
- Week 8
- T Oct 12: Context-free grammars, context-free languages, parse trees, ambiguity, Chomsky Normal Form, Homework 7 assigned
- R Oct 14: Push-down Automata (PDA)
- F Oct 15: Homework 6 due by 12 noon
- Week 9
- T Oct 19: Equivalence of PDA and CFG, CFL.
Homework 8 assigned
- R Oct 21: Non-CFL, Pumping Lemma for CFL.
- F Oct 22: Homework 7 due by 12 noon
- Week 10
- T Oct 26: Pumping lemma for CLF. Chapter 3 begun. Turing Machines.
- R Oct 28: Construction of Turing machines. Turing-decidable languages. Turing-enumerable languages. Homework 9 assigned
- F Oct 29: Homework 8 due by 12 noon
- Week 11
- T Nov 2: Construction of Turing machines. Turing machine variants - multi-tape and nondeterministic.
- R Nov 4: Equivalence of models. Enumerators. Hilbert's 10th problem. Algorithms. Chapter 4 begun. Computational problems as decidable/ recognizable problems on TMs. No homework assigned this week!
- F Nov 5: Homework 9 due by 12 noon
- Week 12
- T Nov 9: Midterm 2: Chapters 0, 1, 2, 3.1, 3.2
- R Nov 11: Decidable languages including examples, language hierarchy, Homework 10 assigned
- F Nov 12: Recitation section meets, but no homework is due
- Week 13
- T Nov 16: Countable vs. uncountable sets, Diagonalization
- R Nov 18: The Acceptance Problem; Undecidable problems; Unrecognizable problems Chapter 5 begun. Halting problem, Reductions.
- F Nov 19: Homework 10 due by 12 noon
- Week 14
- Week 15
v
- T Nov 30: More reductions, Linear Bounded Automata, Decidability of A_{LBA}, Homework 11 due by 10:30am in classroom or Min Shen's mailbox
- R Dec 2: Review of Chapters 4 and 5.
- F Dec 3: Recitation meets as usual
- Week 16 (Final): W Dec 8, 10:30am - 12:30pm
Syllabus: Chapters 0, 1, 2, 3, 4, 5.1 up to and including Theorem 5.9, (pgs 199-200 of 5.2), Linked documents under "Textbooks and Other Resources" section above.
Emphasis is on Chapters 4 and 5.
You are expected to be familiar with all the material covered in the lectures
and in the relevant sections of the textbook.
Attending lectures is highly advisable, because some of the lectures and
homework problems will be drawn from material not in the text, and you will
be responsible for this material.
There will be several homework problem sets, two midterm exams, and a
final exam.
Your final grade will be based on the sum of your problem set, midterms, and
final exam scores.
The following is only a TENTATIVE breakup of the evaluation scheme and is
subject to changes as the course progresses.
- Test 1 (20%).
- Test 2 (25%).
- Final (30%).
- Homeworks and Quizzes (25%): Of the 11 homeworks, the lowest score of each student will be dropped, thus 2.5% for each homework towards the final grade.
The full scale of grades ("A" - "E") will be used.
You may view, but please do not copy or download this file:
Final raw scores on Dec 9, 2010.
Please do not email me for letter grades. I will decide on them probably next week, by which time you will be able to access your official semester grades. I am travelling and out of email contact from this weekend till Thursday 12/16.
I enjoyed teaching your batch! I hope you also found the course useful.
In general there will be no specific reading assignments.
However, the relevant sections from the textbook will be pointed out in
class.
It is recommended that you make yourself familiar with the material prior to
class, and it is a good strategy to read the pertinent sections again right
after class to make sure you understand them.
It is crucial that you continuously stay on top of the material,
because every new topic and every new homework builds on previous results.
If you don't understand the material at the beginning, it will be difficult
to catch up later.
Please do not wait until the last moment to do your homework -- start thinking
about the problems on the day they are handed out!
- Homeworks will usually be assigned on Tuesdays, and the solutions
are due on the Friday of the next week, at the start of
the recitation section. You are welcome to turn in your homework
earlier
to the instructor (me) in class on Tuesdays or Thursdays.
Late homeworks, beyond the start of the recitation section on the
stipulated day, will not be accepted.
-
For the homeworks, we will follow the policy of dropping the lowest homework
score. Hence,
excuses for late or missed homeworks will not be accepted.
-
The solutions to each homework should be written legibly with
your name and the homework number on each sheet of paper.
The solutions must be given in the order of the problems.
Multiple sheets for the same homework must be stapled, or bonded
together so that they will not come apart.
- E-Mail submissions of homeworks are not acceptable.
- Messy and illegible solutions may not be graded.
- If a problem can be interpreted in more than one way, clearly state the
assumptions under which you solve the problem.
-
In writing your homework, you are allowed to consult any book or
published material. If you do so, please cite the bibliographical data of
your source(s). Simply copying a proof is not sufficient;
you are expected to write it up in your own words, and you must be able to
explain it if you are asked to do so.
Your proofs may refer to course material covered earlier,
and to previous homeworks.
Except for this, all results you use must be proved explicitly.
-
The graded problem sets will be returned within two weeks by the TA,
and the solutions will be discussed during the discussion sections.
-
If you have questions about the grading, please talk to the TA.
Graded problem sets that are not picked up in the discussion sections will
be kept by the TA for the duration of the semester, and then discarded.
There will be two in-class mid-term exams during the normal lecture time.
They are tentatively scheduled for October 5 and November 9.
The mid-terms will be cumulative, but they will concentrate on new material.
The final exam will be comprehensive.
In all exams you will be allowed to bring one letter-size sheet of
hand-written notes.
No other material will be allowed.
The work you submit in this course must be the result of your individual
effort.
You may discuss homework problems and general proof strategies or algorithms
with other students in the course, but you must not collaborate in the
detailed development or actual writing of problem sets.
This implies that one student should never have in his or her possession a
copy of all or part of another student's homework.
It is your responsibility to protect your work from unauthorized access.
In writing up your homework you are allowed to use any book, paper, or
published material.
However, you are not allowed to ask others for specific solutions, either in
person or by using electronic forums such as newsgroups.
Of course, during the administration of exams any form of cooperation or help
is forbidden.
Any dishonest behavior will be severely penalized and may lead to failure in
the course.
Academic dishonesty has no place in a university;
it is unfair to the majority of the students. Besides, a proper grounding in
firm ethical behavior is essential to being a good citizen, and
the university is probably the last institution that can instill these
values before you step in to the real world as an independent contributor.