Members‎ > ‎Kelvin C. Buño‎ > ‎

CS 133 - Automata Theory and Computability (Kelvin)


  • Syllabus for this 1st Semester AY 2017-2018
  • [12 Sept 2017] No class meeting today due to QC class suspension from Bagyong Maring.
  • [18 Sept 2017] No class meeting tomorrow (19 Sept 2017, Tuesday). Classes on 21 Sept and 26 Sept will be handled by Sir Francis Cabarle.
  • [17 Oct 2017] Classes and gov't work have been suspended today. 3rd Exam date has been moved to 26 October 2017.
  • [17 Nov 2017] No class meeting on 21 November 2017, Tuesday. Tentative schedule of the 4th exam is on 23 November 2017, Thursday.
  • [3 Dec 2017] Summary of Class Records for HybridUG.
    • Those with TRUE under 4Pass?, congratulations on passing CS133. Your CRS grades are under Temp CRS.
    • Those with TRUE under TakeFE?, you have to take and pass the Finals/Removals on 7 December 2017 (1800H-2000H) to get a 3.00.
    • Those with FALSE on both columns, unfortunately, you have to take CS133 again.
    • You can get your 4th exam starting on Monday, 4 Dec, unless classes are suspended due to transport strikes.
    • Changes can still apply based on 4th exam score complaints/plea.
    • [Update] As some of you pointed out, the LE2 total should have been 4.2. I have revised the linked file to reflect the changes.
    • [Update 2] Just in case you downloaded the revision with the names in that short window, please delete that.
  • [14 Dec 2017] CS133 Hybrid UG Grades. I will upload the grades on CRS by 18 Dec 2017, Monday.

Slides / Materials
1st Exam
Deterministic Finite Automata
DFA Minimization
Nondeterministic Finite Automata
Regular Expressions
Nonregular Languages and Pumping Lemma
Day 01
Day 02
Day 03
Day 04
Day 05
Day 06
 1st Exam: 05 September 2017
 2nd Exam
Introduction to Context-Free Grammars
Designing CFG. Ambiguous CFG.
Chomsky Normal Form
Pushdown Automata
Equivalence of PDA and CFG
Non-Context Free Languages
Day 09
Day 10
Day 11
Day 12
Day 13
Day 14
  2nd Exam: 03 October 2017
 3rd Exam
Introduction to Turing Machines
Variants of Turing Machines
Chomsky Hierarchy
 Decidable Problems
Undecidable Problems
Introduction to Reductions
Day 17
Day 18
Day 19
Day 20 (RR)
Day 21
Day 22
Day 23
  3rd Exam: 26 October 2017
4th Exam
Introduction to Time Complexity
Class P and NP. Polynomial Time Reduction.
Day 24
Day 25
Day 26
 4th Exam: 23 November 2017
 Finals/Removals: 7 December 2017