Teachings‎ > ‎Undergraduate Courses‎ > ‎

CS133 (Automata theory and computability)

Semester 2, AY 2015 to 2016
 by F. Cabarle

The introduction of suitable abstractions is our only mental aid to reduce the appeal to enumeration, to organize and master complexity. — E. W. Dijkstra

  • Welcome to the class web page for CS 133 WFW or WFX! Files and announcements will be concatenated to this list, from oldest (top) to newest (bottom). Stay tuned!
  • 18 Jan 2016: Tentative syllabus can be found HERE.
  • 22 Jan 2016:  Starting today until the end of the sem, we have the following room changes: CS133 WFW (Wed and Fri) room 211 (AIER) changed to room 202 (ERDT room), CS133 WFX (Wed) room 211 changed to room 213 (classroom 1) and (Fri) room 211 changed to room 202.
  • 28 Jan 2016
  • 04 Feb 2016: A regular expression 1(01^+)^* from the slides of day 05 has an incorrect right hand side (i.e. the english description of the expression). Thanks to my yet unnamed student (whom I shall name soon!) who pointed out the mistake in our slides! The right hand side of this expression has now been corrected in the slides.
    • UPDATE: The student who pointed out the mistake is Miguel Martinez. Thank you!
  • 10 Feb 2016: WFW and WFX no class today. Please try the two reviewer files I uploaded in the table to the right. I will try to leave printed copies for you to fotocopy at the 1st floor lobby of DCS. Consultations can be done via email or personally. I will be at room 317 or 319 around 13:00h until 16:00h today. Please be sure to bring on Fri this week your bluebooks for the 1st exam.
  • 23 Feb 2016: Interesting changes in our class schedule to the right. Please have a look.
  • 01 Mar 2016: Exam 1 papers for WFX will be returned tomorrow, while WFW papers were returned Friday last week. Please check that your paper scores tally with my records HERE. You have until a week from now to have your papers corrected.
  • 09 Mar 2016: Those with excused absence for exam 1, special exam 1 is this Friday (11 March), 1pm to 2:30pm, room 317. Also, we have No Class this Friday (11 March). I will upload an exam 2 reviewer on or before that day. I will leave a copy of the reviewer at the photocopy section of DCS.
    • UPDATE: Thanks to Patrick Dominguiano for pointing out an error in my day 17 slides (state diagram of M_2).
  • 12 Mar 2016: After the exam of next week, our next meeting will be on 30 March, due to our attendance to the 16th PCSC and the holy week.
  • 25 Mar 2016: I will return exam 2 papers for WFW and WFX next week. For now you can check your scores HERE. When I return your papers on day x, you have until day x + 7 to have your scores corrected.
  • 07 Abr 2016: CS133 WFW and WFX no class today, 08 April 2016. Please prepare for the exam on 13 April. I uploaded a reviewer for exam 3. Kindly leave your bluebooks with me, tomorrow at room 319.
  • 10 Abr 2016: Those with valid excuses, special exam 2 and 3 will be on 18 April 2016 (Monday), 1pm to 2:30pm at room 317.
  • 12 Abr 2016: Draft 2012 of the UP Diliman Code of Student Conduct can be found online, e.g.
  • 18 Abr 2016: Exam 3 results are now available in our grading sheet HERE. I will return your bluebooks on Wed this week, though you can pass by room 317 or 319 earlier this week to obtain your bluebooks from me also.
  • 05 May 2016: Please check UPDATES of our SCHEDULE table on the right column of this page. EXAM 4 will be in two parts, on 6 May and 11 May. FINAL EXAM is now on 20 May. The release and deadline for the REPORT will be given days before the FINAL EXAM date. Pre-final grades will also be released days prior to FINAL EXAM date.
  • 06 May 2016: Exam 4.1 template is HERE.
  • 12 May 2016: Report template and instructions are HERE. The report will be included in the calculation of the pre-final grade. See our course syllabus for further details of the pre-final grade. I will upload the pre-final grades at least one day before the FINAL EXAM (see table on the right).
    • UPDATE: Report deadline is now 17 May 2016 (Tuesday) at 12PM GMT+8.
  • 18 May 2016: Exam 4 results (both 4.1 and 4.2) are now available in our grading sheet HERE. I will release the report grades on or before tomorrow, 19 MAY (Thu). Further details:
    • You can obtain your exam 4.2 bluebooks from me tomorrow from around 2:30PM till 5PM.
    • Exam 4.2 solutions are at room 319.
    • Since all 4 exams are now available, you can do a simple calculation to determine your chance of taking the final exam, while waiting for your report grades.
    • FINAL EXAM: 20 May 2016 (Friday) at ERDT room
      • WFW at 1PM to 2:30PM
      • WFX at 2:30PM to 4PM
    • Final exam coverage and reviewer: all our past 4 exams and reviewers.
  • 19 May 2016: Pre-final grades are available at our grading sheet HERE. For any doubts concerning their grades, see me at room 317 or 319 tomorrow (Friday) BEFORE 1PM (FINAL EXAM AT 1PM).
  • 24 May 2016: Updated marks now available at our sheet HERE. If you have further doubts or questions, you have until Thursday, 26 MAY 2016 at 5PM GMT+8 in order to consult with me. After 26 May, your grades will be final. 
Date(s)  Lesson(s)Resource(s) 
 20 EneIntroduction Day 01
22 Ene
27 Ene
29 Ene
 Finite automata and regular languagesDay 02
Day 03
Day 04
 03 FebRegular expressions Day 05
05 FebPumping lemma for regular languages Day 06 
10 FebReview/exercises Reviewer 1 (Day 07)
Reviewer 2 (Day 08)
17 Feb EXAM 1  
12 Feb
19 Feb
24 Feb
 Context-free grammars y languagesDay 09
Day 10
Day 11
26 Feb
02 Mar
 Pushdown automataDay 12
Day 13
04 MarPumping lemma for context-free languages  Day 14
09 MarReview/exercises  Reviewer (Day 15)
11 Mar
30 Mar
01 Abr
Turing machines, Turing recognizable and decidable languages   Day 17

Day 18
06 Abr
08 Abr
Turing machine variants, Turing-Church thesis, further topics on computability, reviewDay 19
13 AbrEXAM 3 
15 Abr
20 Abr
22 Abr
DecidabilityDay 20 and Day 21
Day 22
Day 23
27 Abr
29 Abr
Time complexity classes, intractability Day 24
Day 25
04 MayFurther topics on complexity, review Day 26
06 May
11 May
EXAM 4 part 1
EXAM 4 part 2