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

CS 133 - Automata Theory and Computability (2nd Semester, AY2017-2018)

Announcements

  • Syllabus for this 2nd Semester AY 2017-2018.
  • [31 Jan 2018] [THU] No class meeting tomorrow, 1 Feb 2018.

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: 13 Feb 2018
Exercise
 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:
 
 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:
 reviewer
4th Exam
Introduction to Time Complexity
Class P and NP. Polynomial Time Reduction.
NP-Completeness
Day 24
Day 25
Day 26
 4th Exam: 
 
 Finals/Removals: