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.