[Announcements]  [Course Staff]  [Office Hours]  [CS381 or CS481]  [Regrades] 
[Textbooks]  [Homework]  [Exams]  [Lecture Topics]  [Newsgroup] 
Announcements: 


Course Staff: 
 
Office Hours: 


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 inclass 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: 


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. 