CS381 - Fall 2002

Lecture: Monday, Wednesday, and Friday  9:05a-9:55a  Olin Hall 155
[Announcements] [Course Staff] [Office Hours] [CS381 -or- CS481] [Regrades]
[Textbooks] [Homework] [Exams] [Lecture Topics] [Newsgroup]

Announcements:
  • There was a book left in the exam room. If you believe it is yours, email cs381@cs.cornell.edu

  • Final exam solutions are posted below.

  • Homework 13 can be picked up from Beth Howard from 1pm to 4pm Monday, Tuesday, or Wednesday. Identification is required. Listed on your homework 13 are 3 additional numbers: (HMWK SUM, PRELIM1 SCORE, PRELIM2 SCORE) The homework is out of 440 and each prelim has a max of 100. All previous homeworks can still be picked up in the CS undergrad office. If you find your homework sum does not match your graded homeworks, please email cs381@cs.cornell.edu to arrange a time to look over your homework. All unclaimed assignments will be brought to the final exam.

  • Prof. Hopcroft's normal office hours will continue up until the Final Exam. All other office hours are cancelled for the rest of the semester.

  • Brian's office hours (12p-2p) are cancelled tomorrow (12/5)

  • For the question 1 on this week's homework, you should assume that your Turing machine M, on any input, if it halts then it halts after an even number of moves... ie ID1 -> ID2 -> ... -> IDn, n even. Also assume that your tape alphabet and sigma are both {0,1}. This should make it slightly easier for you (and for us to grade).

  • Statistics for Prelim 2: [Mean = 80; Lowest 10th Percentile = 60; Std Dev = 16]

  • At this point in the course the grade statistics are:

    Homeworks: [Mean = 8.77; Lowest 10th Percentile = 6.44]
    Prelim 1: [Mean = 61.94; Lowest 10th Percentile = 43]

  • Unclaimed exams may be picked up from Upson 5147. Photo ID is required.

  • From this week's homework forward, TAs will put their initials on your graded homeworks. For regrades, you may see this TA during their office hours or send email to setup an appointment with them. You also still have the option of providing a written explanation and resubmitting the following week. Whichever you choose to do, you still have only one week from the day it was handed back.

  • You are encouraged to work in groups to solve the homework problems, however, solutions must be written in your own words and you must fully understand everything that you submit. Students suspected of voilating this will be asked to explain their homework solutions in person.

  • Homework is VERY important; at least half of your final grade will be based on your homework scores. Therefore it is very important that homework is done carefully and legibly. Unreadable homeworks will be returned and will receive no credit.

  • Homeworks not picked up after class on the day it is handed back will be in Upson 303 which is open during regular business hours.

  • Please place your netID on the front of each homework problem you submit.

  • In addition to the newsgroup, there is an email list that has been setup to correspond with the course staff. Please send all course related questions to cs381@cs.cornell.edu rather than directly to Professor Hopcroft or to one of the TAs. You are likely to get a faster response by using this address rather than emailing one of us directly.

Course Staff:
  Office Email Address
Professor HopcroftUpson 5144jeh@cs.cornell.edu
Xiangyang LanUpson 4158xylan@cs.cornell.edu
André AllavenaRhodes 421andre@cs.cornell.edu
Mark RobsonUpson 328robson@cs.cornell.edu
Omar KhanUpson 328ohk2@cornell.edu
Brian J KulisUpson 328bjk24@cornell.edu

Office Hours:
Monday 11am-12pm Prof. Hopcroft (Upson 5144)
Tuesday 2pm-3pm André (Rhodes 421)
3pm-4pm Prof. Hopcroft (Upson 5144)
6:30pm-8pm Xiangyang (Upson 328)
Wednesday 11am-12pm Prof. Hopcroft (Upson 5144)
12pm-1pm Omar (Upson 328)
2:30pm-4pm Mark (Upson 328)
Thursday 12pm-2pm Brian (Upson 328)
2pm-3pm André (Rhodes 421)
3pm-4pm Prof. Hopcroft (Upson 5144)
6pm-8pm Omar (Upson 328)
Friday 11am-12pm Prof. Hopcroft (Upson 5144)

CS381 -or- CS481:

 CS381 and CS481 follow roughly the same syllabus, but CS481 is somewhat faster paced and goes into more depth. It is meant for more theoretically inclined students, grad students, and undergrads bound for grad school. Corrective shifting is encouraged in the first few weeks of the semester.

Regrades:

 To apply for a regrade, please attach a note to the assignment explaning the reason you feel it should be regraded and hand it in with the next week's homework assignment. Assignments will not be eligible for a regrade unless the request is recieved with the homework following the week in which it was handed back; after that, grades are final.

Textbook:

 Introduction to Automata Theory, Languages, and Computation / John E. Hopcroft, Rajeev Motwani, Jeffery D. Ullman -- 2nd Edition

Homework:

 (All problems from Hopcroft, Motwani, and Ullman unless otherwise specified)

Assignment #1: 2.2.1 , 2.2.2 , 2.2.4 , 2.2.5a [Solutions]
Assignment #2: 2.3.1 , 2.3.4 , 2.4.1 , 2.4.2 [Solutions]
Assignment #3: 3.1.1c , 3.1.2b , 3.1.3a,b , 3.1.4a,b [Solutions]
Assignment #4: 4.1.1e , 4.1.2c,d,e , 4.2.6 [Solutions]
Assignment #5: 4.1.2h , 4.2.1 , 4.2.6 by homomorphism and closure properties [Solutions]
Assignment #6: 4.4.2 , Give a CFG for: (a^i)(b^j)(c^k) where (i=j) or (i=k) or (j=k) , Give a CFG for: (a^i)(b^j) where (i!=j) , Give a CFG for: x#y where x,y belong to {a,b}* and the inverse of x is a substring of y [Solutions]
Assignment #7: Give a CFG for: {0,1}*-{010010001...10^i1 | i>=1} , Give a CFG for: the set of all regular expressions over the alphabet {0,1} [Solutions]
Assignment #8: 6.3.2 , 6.3.4 , 6.3.5 [Solutions]
Assignment #9: 7.1.3 , 7.2.1b,e,f , 7.3.1a,b [Solutions]
Assignment #10: 7.4.1a,b , 7.4.3c [Solutions]
Assignment #11: 8.2.1c , 8.2.2c , 8.2.3 [Solutions]
Assignment #12: 9.2.2b,c , 9.2.4 , 9.2.5 , 9.2.6 [Solutions]
Assignment #13: 1. Let M be a Turing Machine and x be a string. Develop the set of productions for CFGs G1 and G2 such that the intersection of L(G1) and L(G2) is the valid computations of M on x; 2. Why is determining if the intersection of L(G1) and L(G2) is empty undecidedable for arbitrary CFGs G1 and G2?; 3. Why is L(G) = Sigma-* undecidable for an arbitrary CFG G? [Solutions Part 1] [Solutions Part 2]

Exams:

 (Both prelims will be in-class examinations)

Prelim #1: October 7th   [Solutions]
Prelim #2: November 8th   [Solutions]
Final Exam: December 19th [12:00 - 2:30] (location: Olin 155)   [Solutions]

Lecture Topics:
August 30th Introduction to Notation, Alphabets, Strings, Empty String, Sets, Empty Set, Countably Infinite Sets, Intro to Diagonalization, Definition of Finite Automata
September 2nd Deterministic Finite Automata: Formal definition, Extending delta function to (Q x SIG*), Examples; Non-deterministic Finite Automata: Informal definition, Examples
September 4th Introduction to NFA-DFA conversion, Formal definition of NFAs, Extension of Delta function to (Q X SIG*) for NFAs, Introduction to NFAs with epsilon transitions, Reversing of finite automata's
September 6th (Hartmanis) Subset Construction; How to convert a NFA to an DFA: Examples, Theorem, Brief intuitive discussion of the proof
September 9th Applications of NFAs and conversion to DFAs; Relationship between DFAs, NFAs, Epsilon-NFAs; Epsilon-closures
September 11th Regular Expressions: Definition, Operators, Examples
September 13th Notation review, Examples of Regular Expressions, Conversion of DFAs to Regular Expressions
September 16th Continuation of Examples, Converting Regular Expressions to Automata
(notes on DFA to Regular Expression conversion are here)
September 18th Converting Regular Expressions to Automata, Regular Expression Operators, Showing sets are not Regular via the Pumping Lemma
September 20th Pumping Lemma Examples, Closue Properties: Union, Intersection, Complement, -, Reverse, Homomorphisms
September 23rd Homomorphisms, Closure under Homomorphisms - Proof with Regular Expressions & Machines, Inverse of Homomorphisms
September 25th Review of homomorphisms, Closure under inverse homomorphisms, Using closed operations to show languages regular
September 27th Examples of using closed operations to show languages regular
September 30th Prove ValidComp(M) is valid using homomorphism, O(n) notation, Decision Procedures, Prove Emptiness Problem, Membership Problem and Equivalence Problem in Regular Language are all decidable.
October 2nd Testing equivalence of states, DFA minimization
October 4th Definition and Example of Context Free Grammars, Derivations of CFGs, Definition of Context Free Languages
October 7th < Prelim #1 >
October 9th Review of prelim, CFL example
October 11th Conversion of Automata to CFGs, Theorem: Regular Languages are proper subsets of CFLs, Theorem: CFLs are not closed under intersection and complement
October 16th Definition of PDAs, Equivalence of PDA accepting by final state and PDA accepting by empty stack
October 18th Construction of a CFG G for a PDA M such that L(G) = N(M), and proof of the equivalence
October 21st Chomsky Normal Form
October 23rd Converting CFG into CNF; The Pumping Lemma for CFL
October 25th Application of the Pumping Lemma for CFL's; The Substitution Theorem for CFL; Applying the Substitution Theorem to show the closure properties of CFL under union, concatenation, *, +, Homomorphisms, and Reversal; CFL is not closed under Intersection and Complement
October 27th More on Closure Properties
October 29th Decision Procedures for CFL's; Testing Membership in a CFL; Testing Emptiness of CFL's
November 1st Computer Programs are Countably Infinite; Diagonalization Lemma; Definition of Recursive Language Sets; Definition of Recursively Enumerable Language Sets
November 4th Proper contain Relation between Regular Set, CFL, Recursive Set and Recursively Enumerable Set; Definition and Notation of the Turing Machine; Instantaneous Descriptions for Turing Machines
November 6th Multiple Tracks, Multitape TMs, Equivalence of One-Tape and Multitape TMs, Nondeterministic Turing Machines, Simulating a TM by Computer, Simulating a Computer by TM
November 8th Turing Machines with Semi-infinite tapes, Multitask Machines, Counter Machine and its power, The Diagonalization Language, Proof that the Diagonalization Language is not RE
November 11th Review of Prelim 2, Decidability problems and TMs, The Halting Problem
November 13th The Halting Problem is Undecidable, Rice's Theorem, Undecidable problems for CFLs
November 15th The Diagonalization Language is not RE; {(M,x) | TM M halts on string x} is RE but not recursive (Halting Problem) and the complement is not RE; Proof that the Halting Problem is not recursive (decidable) by reduction
November 18th Halting Problem is RE but not recursive, Rice's Theorem and properties of the RE languages, Proof of Rice's Theorem by reduction
November 20th ValidComp of TMs with Intersection of CFLs, the emptiness of the intersection of two CFLs is undecidable, L(G) = Sigma* for CFLs is undecidable, the equivalence of 2 CFLs is undecidable
November 22nd The class P and examples: Membership in CFL, Prime, etc.; The class NP and examples: Hamiltonian-Circuit Problem, Factorization, Conjunctive Normal Form, Clique, etc.; Polynomial-Time reduction from CNF to Clique Problem
November 25th NP-Completeness of #-CNF problem, Proof of Cook's Theorem

Newsgroup:

 There is a newsgroup cornell.class.cs381 established for this course. It is intended for discussing CS381 related topics, interesting problems (NOT homework solutions), complaints, suggestions, etc. You can learn more about newsgroups here.



Mark Robson
Last modified: Thu Dec 19 15:30:22 EST 2002