CS 133 - Automata Theory and Computability


Announcements

  • January 17, 2018 - Welcome to the official site of the CS 133 (Automata Theory and Computability) class of Nestine Hernandez. Here you will find materials you may need for the class and announcements regarding future activities. 
  • Consultation Hours: 
    • TTh 4-6pm (Rm 319)
    • in case you want to consult on a different time, please email me (nshernandez@dcs.upd.edu.ph) first to check for availability
  • The following students will be transferred from THW to THW-1:
ALMEROLSON ROY
CRUZEUNICE ANGEL
DEL CAMPOADRIAN RAY
GONZALESAIMEE NICOLE
JUICOJULES GERARD
MANAOATNEIL MARTIN
MAYOLMICHAEL PIO
QUIAMBAOLORENZO
REDENADANA KATHLEEN
REGARDEPATRICIA ANN
SANTIAGOPAULO GABRIEL
SUNJOHN CHRISTIAN
TABERDODOM HELDER

  • 17 April 2018 - Please group yourselves for the reporting at the end of the semester. For each class, there would be three groups composed of 5, 5 and 4 students. Each group should submit the list of group members and a list of proposed topics for reporting (minimum of three). You can choose any topic related to Automata Theory and Computability as long as it was not yet taken in class. Please write in a sheet of paper to be submitted on 19 April 2018.



 DateLesson Slides / Materials
01/16/2018IntroductionIntro
01/18/2018
(Deterministic) Finite Automata and
Regular Languages
DFA
 01/23/2018 DFA Minimization 
Closure on Class of Regular Languages
minDFA
01/25/2018Nondeterministic Finite Automata
Equivalance of DFA and NFA
NFA
 01/30/2018 Regular Expressions
Equivalence of RegEx and NFA/DFA
RegEx
02/01/2018Review/Exercises reviewer
02/06/2018EXAM 1 
 02/13/2018 Pumping Lemma for Regular LanguagesNon-reg
02/15/2018
02/20/2018
Context-Free Grammars and LanguagesCFG
CNF
02/22/2018
02/27/2018
(Nondeterministic) Pushdown Automata 
Equivalence of nPDA and CFG; dPDAs
nPDA
CFG vs nPDA vs dPDA
03/01/2018 Review/Exercises reviewer
 03/06/2018EXAM 2 
03/08/2018  Pumping Lemma for Context-Free LanguagesnonCFL 
03/13/2018
03/15/2018
Turing Machines
Variants of TM
TM
varTM
 04/03/2018Hierarchy of Languages
Review/Exercises 
chomsky hierarchy
reviewer
 04/05/2018  EXAM 3 
04/10/2018
04/12/2018
04/17/2018
DecidabilityChurch-Turing
Decidability
Reducibility
04/19/2018Time Complexity Classes
(P,NP,NP-complete)

04/24/2018Intractability 
04/26/2018Review/Exercises  
05/05/2018EXAM 4
05/08/2016

 REPORT
TBAFINAL EXAM 

  • Syllabus can be downloaded here.