CS 133 - Automata Theory and Computability

Announcements

  • January 20, 2016 - 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 2:30-6pm
  • January 21, 2016 - Starting tomorrow, we will have our classes at CLR 2 every Friday and at CLR 3 every Wednesday.
  • February 16, 2016
    • Reminder: FIRST LONG EXAM is tomorrow at CLR3, 10-11:30 am.
    • There are still 3 students who haven't submitted bluebooks for the exam. Make sure you bring a bluebook tomorrow, else you'll be wasting precious time trying to look for one.
  • April 19, 2016 - Results of 2nd LE is already available. I'll be returning them during class on Wednesday. But if you want to know your score asap, just send me an email. 
  • May 03, 2016 - We won't have classes tomorrow but I will be available for consultation at Rm. 319. Those who have not submitted bluebooks for the exam on Friday, please submit them ASAP.
  • May 10, 2016 - 
    • Schedule of Reports:
      • Wed (11 May)
        1. Applications of Automata in Games
        2. Linear bounded Automata and Context-Sensitive Languages
        3. Computational Complexity of the Protein Folding Problem
      • Friday (13 May)
        1. Motion Grammar
        2. Membrane Computing
        3. Busy Beaver
    • Limit the report to 20-25mins/group.
    • Don't forget to cite your references.
    • On the last slide of your presentation, list down the contribution of each member of the group.
    • After the report, send your presentation slides via email to nshernandez@dcs.upd.edu.ph with subject CS133 Report.
  • May 18, 2016
    • You may check out your class standing here.
    • Please email me if there are any discrepancies.
    • Those who are taking the final exam may do so on 20 May 2016, Friday 9:30-11:30 am. Look for me at Rm 319 or 317.
  • May 20, 2016
    • Results of Final exam:
      • 2013-00167 - passed (70%)
      • 2013-00809 - passed (62%)
      • 2014-30506 - failed (54%)

 DateLesson Slides / Materials
01/20/2016IntroductionDay 1 slides
01/22/2016
(Deterministic) Finite Automata and
Regular Languages
Day 2 slides
 01/27/2016 DFA Minimization 
Closure on Class of Regular Languages
Day 3 slides
01/29/2016Nondeterministic Finite Automata
Equivalance of DFA and NFA
Day 4 slides
 02/03/2016 Regular Expressions
Equivalence of RegEx and NFA/DFA
Day 5 slides
02/05/2016Pumping Lemma for Regular LanguagesDay 6 slides
02/10/2016 Review/Exercises Reviewer 
02/17/2016EXAM 1 
02/12/2016
02/19/2016
02/24/2016 
Context-Free Grammars and LanguagesDay 9 slides
Day 10 slides
Day 11 slides
02/26/2016
03/02/2016
(Nondeterministic) Pushdown Automata 
Equivalence of PDA and CFG
Day 12 slides
Day 13 slides
03/04/2016
 
Deterministic PDA
 Pumping Lemma for Context-Free Languages
 Day 14 slides
03/09/2016  Review/Exercises  Reviewer
 03/11/2016 EXAM 2 
03/30/2016
04/01/2016
04/06/2016
Turing Machines
Day 17 slides
Day 18 slides
Day 19 slides
 04/08/2016 EXAM 3 (PART 1)
Hierarchy of Languages
Reviewer
Day 20 AB 
04/13/2016
04/15/2016
04/20/2016
DecidabilityDay 21
Day 22
Day 23
04/22/2016
04/27/2016 
Time Complexity Classes
(P,NP,NP-cpmplete)
Day 24
Day 25
04/29/2016Intractability  Day 26
05/04/2016 Review/Exercises  
05/06/2016EXAM 3 (PART 2)
05/11/2016
05/13/2016 
 REPORT 
05/20/2016FINAL EXAM 

  • Syllabus can be downloaded here.