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)
  • 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




 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
 01/30/2018 Regular Expressions
Equivalence of RegEx and NFA/DFA

02/01/2018Review/Exercises 
02/06/2018EXAM 1 
 02/13/2018 Pumping Lemma for Regular Languages
02/15/2018
02/20/2018
Context-Free Grammars and Languages
02/22/2018
02/27/2018
(Nondeterministic) Pushdown Automata 
Equivalence of PDA and CFG

03/01/2018 Review/Exercises 
 03/06/2018EXAM 2 

03/08/2018  Pumping Lemma for Context-Free Languages 
03/13/2018
03/15/2018
03/20/2018
Turing Machines

 03/22/2018Hierarchy of Languages
Review/Exercises 
 04/03/2018  EXAM 3 
04/05/2018
04/10/2018
04/12/2018
Decidability
04/17/2018
04/19/2018
Time 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.