Members‎ > ‎Jan Michael C. Yap‎ > ‎

CS 133 - Automata Theory and Computability

Announcements

  • **NEW** November 17, 2015 - Exam 4 scores up. I will be emailing my comments in a bit. Also, here's your prefinal class standing, which also serves as the exemption list for the finals. Again, the Final Exam is on November 26, Thursday, during class hours. Email me if you have clarifications regarding the information posted. Please be guided accordingly.
  • November 15, 2015 - UPDATE: Problem Set 3 scores up. If you noticed, there are no deductions here as I have decided to waive off the late submission penalty for this Problem Set. I'll be emailing those with comments within the day. Also, here's your post PS 3 class standing. If your "Min Exam 4 for Exemption" is "N/A", it means that you are already exempted from taking the finals regardless of the outcome of Exam 4. Speaking of Exam 4, kindly read the next paragraph (if you haven't read it yet, that is):
As brought up by Mr. Levi Gruspe, and after checking several references, it seems that the (un)decidability of D is still under question. Also, upon checking how I did the reduction, it turns out that it was actually wrong to begin with. As such, Item 1 is now a bonus item. Sorry for the mistake. :)
  • November 14, 2015 - Correction for Item 1 of Exam 4: the polynomial should be over x *and y*. Thanks to Mr. Patrick Domingo for the heads up.
  • November 12, 2015 - Exam 4 questionnaire up. ABSOLUTE deadline of submission (via email) is on Monday, November 16, 12nn. I haven't finished checking your PS 3 yet, although I aim to release the results and class standing by Monday at worst.
  • November 2, 2015 - Here are your post-Exam 3 class standing. Blank entries in your Exam 3 mean that I did not receive any submission during the deadline. I will be handing out the papers on Tuesday, November 3, during class hours. In addition, as a clarification to the number of items in Problem Set 3, there are only 5 items there, and item 4 is only considered one item. This means that the only split allowed in this case is 3 items to 2 items. Please be guided accordingly.
  • October 29, 2015 - Problem Set 3 questionnaire now up
  • October 26, 2015 - Problem Set 2 Scores now up. I will be sending you the comments in a bit. I have also finished checking your Exam 2, and will be handing out the checked sheets tomorrow before lecture starts. Also, here is the post-PS 2 class standing for both classes. FG* represents your final grade should the semester end today. Also, I have not factored in yet in there invalidated exams due to non-submission of PS. Please be advised accordingly. See you tomorrow. :)
  • October 24, 2015 - Problem Set 1 Scores now up (FINALLY). I will be sending you (or a representative of your pair) an email if I have comments regarding your PS 1 submission. Nonetheless, if you have questions regarding the scores, feel free to e-mail me. Please be guided accordingly.
  • October 22, 2015 - I have consulted several references and people regarding Problem Set 2 item 7, and with finality, the language is in fact CONTEXT FREE. I will still abide by the announcement that it is considered a bonus item, but extra points will be given if a correct answer will be given. Please be guided accordingly.
  • October 8, 2015 - Problem Set 2 Questionnaire now up.
  • October 5, 2015  - Reviewer for Exam 2 up. UPDATE: The "either-or" statement in the condition set for the language in item 3 is a simple OR statement. Therefore, strings where p = q = r is acceptable.
  • September 28, 2015 - We will have classes tomorrow (FINALLY!), September 29, 2015, normally (i.e. 8:40am-10:15am for THR and 10:40am-11:15am for THU). Please be guided accordingly. See you all tomorrow. :)
  • September 18, 2015 - Firstly, I would like to apologize for the abrupt cancellation of classes yesterday, and for posting this announcement late. Regarding Problem Set 1, I have made a revision to Item 6 of the questionnaire, owing to the intractability of answering the original question, so check the link again for the revised questionnaire. In addition, the deadline of submission for Problem Set 1 is thus moved to September 25, Friday, 11:59pm. Secondly, our next class will be on September 24, Thursday next week. Additionally, we will have extended periods starting next week (THR: 8:35-9:55; THU: 10:05-11:25) to make up for lost time. Please be guided accordingly. See you all next week! :)
  • September 8, 2015 - Problem Set 1 Questionnaire now up.
  • September 3, 2015 - Exam 1 Answer Key up. Problem Set 1 specs would be released on September 8, 2015.
  • September 2, 2015 - UPDATE: Due to limited number of seats in the classroom, I would have to enforce that a student can only take the exam on his/her officially enrolled class schedule. This means that only THR students are allowed to take the 8:45am exam, and only THU students are allowed to take the 10:15am exam. Hoping for your understanding, and please be guided accordingly. Partial answer key for Exam 1 reviewer up. Some items were not deliberately answered, and some were only given hints on how to proceed with the answer.
  • September 1, 2015 - Reviewer for Exam 1 up. See right hand side under Slides/Materials column. For Exam 1 and subsequent Exams, we will start at 8:45am until 10:00am for the THR class, then 10:15am until 11:30am for the THU class. Again, no need to bring bluebooks, just blue or black pens. Study well, and see you on Thursday. :)
  • August 27, 2015 - I have made a monumental mistake in some of the things I mentioned regarding the pumping lemma for regular languages. Because of that, I need to reset in the explanation of the examples on our Tuesday (September 1) session, and for us to cover more ground, I'll have to stretch the period a little bit so we could also cover review for Exam 1. So on Tuesday, classes are from 8:35am to 9:50am for THR and 10:05am to 11:20am for THU. My sincerest apologies for the misstep, and hoping for your understanding. Hope you enjoy the long weekend, and see you on Tuesday. :)
  • August 17, 2015 - We will now hold classes in AIER starting tomorrow, August 18, until further notice. See you there! :)
  • August 4, 2015 - This is the website for the CS 133 (Automata Theory and Computability) class of Jan Michael Yap. Announcements and files pertinent to the class will be posted here.

DatesLesson Slides/Materials
08/04/2015IntroductionSlides
08/06/2015
08/11/2015
08/13/2015
Finite Automata and Regular Languages
Slides:
Part 1
Part 2
Part 3
08/18/2015
08/25/2015
Regular Expressions
Slides
08/27/2015
09/01/2015
 Pumping Lemma for Regular Languages
Slides
09/03/2015
EXAM 1Answer Key
Reviewer
09/08/2015
09/25/2015
 PROBLEM SET 1Scores
Questionnaire
09/08/2015
09/10/2015
09/15/2015
Context-Free Grammars and Context-Free Languages
Slides:
Part 1
Part 2
Part 3
09/29/2015
10/01/2015
Pushdown Automata
Slides:
Part 1
Part 2
10/01/2015
10/06/2015
Pumping Lemma for Context-Free Languages
Slides
10/08/2015
EXAM 2Reviewer
10/08/2015
10/23/2015
 PROBLEM SET 2Scores
Questionnaire
10/13/2015
10/15/2015
Turing Machines
Slides

10/15/2015
10/20/2015
Turing-Recognizable and Turing-Decidable Languages
Slides
Reading
10/20/2015
10/22/2015
Variants of Turing Machines
Slides
10/22/2015
Church-Turing Thesis
 Slides
10/27/2015
EXAM 3
 Questionnaire
10/29/2015
 11/09/2015 
PROBLEM SET 3 Questionnaire 
10/27/2015
10/29/2015
11/03/2015

Decidability
Slides:
Part 1
Part 2
Part 3
 
11/05/2015
11/10/2015
11/12/2015
IntractabilitySlides:
Part 1
Part 2
Part 3
11/12/2015EXAM 4 Questionnaire
 11/26/2015  FINAL EXAM 

  • Syllabus can be downloaded here.
  • Copy of the 2012 Code of Student Conduct can be downloaded here.