CS 133 - Automata Theory and Computability


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

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


1-1:25pm Parikh's Theorem

provide at least: definitions,significance,proof


1:30-1:55pm PageRank and Its Complexity

provide at least: definitions,significance,proof


2-2:25pm Automata Theory and Artificial Intelligence

provide at least: definitions,specific examples,significance



2:30-2:55pm Greibach Normal Form

provide at least: definitions,conversion algo,compare/contrast with CNF (advantages/disadvantages),uses


3-3:25pm Mealy and Moore Machines

provide at least: definitions,significance,compare/contrast Mealy and Moore, advantages/disadvantages, specific examples


3:30-3:55pm Cellular Automata

provide at least: definitions,significance,specific examples,applications


We'll move the reporting schedule to May 10 instead of May 8. But you'll be submitting a written report on May 8.


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.



  • Syllabus can be downloaded here.


2015-09240 68% (final grade 3.0)

2015-03088 54% (final grade 5.0)