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

CS 133 - Automata Theory and Computability (Kelvin)

Announcements

  • Syllabus for this 1st Semester AY 2017-2018
  • [12 Sept 2017] No class meeting today due to QC class suspension from Bagyong Maring. http://cnnphilippines.com/news/2017/09/11/walang-pasok-Sept-12.html
  • [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.

Coverage
Topics
Slides / Materials
1st Exam
Introduction
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
Transducers
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
 reviewer
4th Exam
Introduction to Time Complexity
Class P and NP. Polynomial Time Reduction.
NP-Completeness
Day 24
Day 25
Day 26
 4th Exam: 23 November 2017