The right way to teach and learn math -- my new book: Rediscovering Mathematics


UIC - CS 301 - Languages and Automata

Shai Simonson    Room: 1216 SEO

Email:  shai@stonehill.edu

Homepage: http://web.stonehill.edu/compsci/shai.htm


Lectures:  MWF 1:00 - 1:50,  Room SES-238

Office Hours:  I will be in my office (1216 SEO) every Monday and Wednesday from 9:30 - 11:30.  You are welcome to see me anytime I am in, and if you cannot make those hours, feel free to email me about another time.

Description:  A theoretical treatment of what can be computed and how fast it can be done. Applications to compilers, string searching, and control circuit design will be discussed. The hierarchy of finite state machines, pushdown machines, context free grammars and Turing machines will be analyzed, along with their variations. The notions of decidability, complexity theory and a complete discussion of NP-Complete problems round out the course.

Text:  Introducing the Theory of Computation  by Wayne Goddard,  Jones and Bartlett Publishers, 2009.

Exams:  There will be 6 quizzes (40% total) and one final examination (35%).  Each quiz will be worth 20 points and the lowest quiz grade will be droppedQuizzes will be taken in discussion sections and administered and graded by the TAs.

Teaching Assistants:  The teaching assistants will grade your homework assignments and quizzes, and answer questions at labs under my guidance and with my instructions.  If you have a question or complaint about a HW or quiz grade, and you are unable to resolve it with the TA, please see me for help. 

Discussion Sections:  The TAs will alternate between giving quizzes, and reviewing HW and quizzes.  You are expected to attend the discussion section for which you are signed up.  The TAs will take attendance and it will be counted in your HW grade.  Lab times:  11 AM meets at 208 Burnham, and 12 PM meets at 117 Taft.

The teaching assistant this semester is:  Iman Mirrezaei  Office Hours:  1212 SEO Tuesday 3:30-5:30

Assignments:  Homework assignments will be worth 25% of your grade (6.25% each assignment).   The HWs are meant to force you to study and practice.  If you work hard and meet with the TAs and myself, you can always be sure to work through every problem and get full credit. You may work with a partner on the homework and submit one assignment for both of you.  If you choose to do this, then stick together all semester.  It is easier to work with a partner but you will get less practice.

Grades: 
I count your HWs and lab attendance for 25%, quizzes for 40%, and the final as 35%.   You can guarantee an A, B, C, D grade with at least a 90, 80, 70, 60 percent respectively.  I may lower these numbers (in your favor) at the end of the semester if I feel a curve is justified.

Academic Honesty: 
I value hard work and honest effort.  If you are working with a partner, make sure the TAs know you are submitting work as a group.  If you use any resource on the Internet to help you with your HW, or you get a hint from a fellow student or TA, you must rewrite the idea in your own words and reference your source.   It is especially easy to check if you copy a solution in theory of computation since many online sites use different notation than I use in class. Copying work, or rewriting it in your own words without any reference, has potential serious consequences, including failing the course.  Moreover, this kind of dishonesty will not prepare you properly for the quizzes and final exam.  If a TA reports that your HW violates academic integrity guidelines, I will take a look and if I agree, then you will get a zero on that assignment.  If it happens twice, then I will follow the school's more serious policies.   Read my academic integrity guidelines before you hand in any written work.

Special Dates:    April 16 and 21 are Jewish holidays and I will not lecture on those dates.  There will be a substitute lecturer, or a quiz.


Assignments

assignment 1 assignment 2 assignment_3 assignment 4

Resources

Alan Turing Page    Funny Halting Poem     A Real Turing Machine       Index of ADUni Lectures     YouTube of My Theory Lectures    Brzozowski's FSM Minimization Algorithm      Syntax Diagrams for Pascal


Brief Syllabus

Week Topics Reading
1 Introduction:  Languages, Grammars, and Automata (Machines). Fundamental connection to computer science.  Applications.   5
2 Regular Sets:  Finite State Machines,  Regular Expressions, and Regular Grammars 1, 2, 8.1
3 Nondeterminism and equivalence of NFSM's to DFSM's.  Other variants of FSM's 3
4 Closure Properties of Regular Sets - a constructive review.  Encoding FSMs, diagonalization, and a non-regular set.
4.1- 4.2
5 The Pumping Lemma - How to show that a set is not Regular. 4.3
6 Decision Algorithms for FSM's.  (Problems whose inputs are FSM's.)  Decidability. 4.2
7 Context Free Languages:  Context Free Grammars and Applications, Syntax Diagrams.
6
8 Pushdown Machines - Deterministic versus nondeterministic.  7
9 Chomsky Normal Form - Three applications.   Equivalence of NPDM and CFL's. 8, 9.1
10 Closure Properties of CFL's and DCFL's.  Decision Algorithms for CFL's.  Applications to compilers. 10.1, 10.2
11 The CFL Pumping Lemma - Showing that a set is not context free. 9.2
12 Turing Machines and Variants:  Multitape, nondeterminism, multidimensional, 2-stack machines. 11, 12
11 Decidability:  The Halting Problem.
13, 14
12 Reductions and more Undecidable problems, Post's Correspondence Problem, CFL equivalence, CFL ambiguity.
15
13 Computational Complexity - Measuring the time and space requirements of decidable problems. 17, 18
14 The computational classes P and NP.  The concept of an NP-Complete Problems.  Reductions revisited. 17.6, 19