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.
  • 02 May 2018 - For the group reports:
            THW: 
                1-1:25pm             Parikh's Theorem  
                                            provide at least: definitions,significance,proof     
                                            (Aceron,Alarcon,DelPrado,Granda,Mendoza)

                1:30-1:55pm        PageRank and Its Complexity
                                            provide at least: definitions,significance,proof  
                                            (Abenojar,Cancio,Dionio,Dumas,Manguiat)

                2-2:25pm             Automata Theory and Artificial Intelligence
                                            provide at least: definitions,specific examples,significance
                                            (Dalisay,Dioso,Mediarito,Ramos)

            THX:
                2:30-2:55pm        Greibach Normal Form
                                            provide at least: definitions,conversion algo,compare/contrast with CNF (advantages/disadvantages),uses
                                            (Aquino,Capiral,Jose,Pega)

                3-3:25pm             Mealy and Moore Machines
                                            provide at least: definitions,significance,compare/contrast Mealy and Moore, advantages/disadvantages, specific examples
                                            (Balingit,Bilaw,Kasilag,Villamera,Zaguirre)

                3:30-3:55pm        Cellular Automata
                                             provide at least: definitions,significance,specific examples,applications  
                                            (Barrameda,Chan,Faelnar,Fernandez,Sanchez)

We'll move the reporting schedule to May 10 instead of May 8. But you'll be submitting a written report on May 8. 
(updated:03may2018) 
The oral report should take at most 25 minutes and should at least cover the points I mentioned above. 
The written report is expected to be more detailed than the oral report. Don't forget to cite your references. Include at the last section a list of contributions of each member of the group.

03 May 2018 - FINAL EXAM is on 24 May 2018, Thursday, 4-6pm.

08 May 2018 - You may submit your written report  thru email (nshernandez@dcs.upd.edu.ph) with subject: CS133 written report (your section). Deadline is today 11:59pm.
You may also get your 3rd exam bluebooks from me at Rm 317 (ACLab) today from 1 to 4 pm.

18 May 2018 - I've already finished checking your LE4. But I still need to incorporate your scores for the report before I can release your class standing. Class standing will be posted here on Monday, at the latest.

19 May 2018 - Class standing: THW and THX

20 May 2018 - You may get the LE4 from me on Tuesday, 22 May, 1-3pm at Rm 319.

24 May 2018 - Reminder: FINAL EXAM IS TODAY, 24 May 2018, 4-6pm, CLR2.

EXAM RESULT:

THW
2015-05400     60% (final grade 3.0)
2015-13937     66% (final grade 3.0)
2015-05408     54% (final grade 5.0)
2015-12898     50% (final grade 5.0)
2016-00207      72% (final grade 3.0)

THX
2015-09240   68% (final grade 3.0)
2015-03088    54% (final grade 5.0)


 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)
P=NP?
04/24/2018Intractability NP-completeness
04/26/2018Review/Exercises reviewer 
05/03/2018EXAM 4
05/08/2018
05/10/2018
submission of written report
 ORAL REPORT

05/24/2018FINAL EXAM 

  • Syllabus can be downloaded here.