Teachings‎ > ‎Undergraduate Courses‎ > ‎

CS133 (WFU and WFW) S1 AY2017--2018



The introduction of suitable abstractions is our only mental aid to reduce the appeal to enumeration, to organize and master complexity. — E. W. Dijkstra
  • 10 Ago 2017: Links to syllabus, academic calendar are now available. First of several slides and required readings (or RR) are now available also.
  • 01 Sep 2017: New DATE for EXAM1 is now 06 September, instead of 01 September.
  • 14 Sep 2017: ALL students please check your bluebook marks versus my record HERE for exam1. You have till next week for corrections. Answer keys are posted at room 317.
  • 02 Oct 2017: Required reading 2 and 3, i.e. RR2 and RR3, now available.
  • 12 Oct 2017: All lecture slides for exam 3 (till day 23) are now uploaded. Reviewer for exam 3 is also uploaded. Be sure to answer exercises in the Sipser book till Chapter 5 for exam 3 also.
    • Day 23 slides update: corrected and improved proof for L_{ne} not in REC.
  • 17 Oct 2017: No class on 18 October, Wednesday, to make room for more preparation for exam 3. Consultations or corrections of exam 2 will be entertained during class hours at room 317 or 319.

 Weektopics Slides / Materials
regular languages and finite automata, regular operations.
Day 1
Day 2
Day 3
Nondeterministic finite automata,
equivalence of DFA and NFA,
Minimization of states. 
Day 4
Day 5
Regular expressions,
equivalence of regular expressions to finite automata.
Nonregular languages, Pumping lemma,
Review for exam 1,
EXAM1 (06 September 2017)
Day 6 
exam1 reviewer
 5 CFLs, CFGs,
CFG in CNF, closure properties
Day 9
Day 10
Day 11 
CFGs and PDAs
 Day 12
Day 13
problem set for exam2
NonCF languages,
Review for exam2 
Day 14 
EXAM2 (27 September 2017)  
Turing machines, transducers,
Variants (e.g. multitape, nondeterministic),
Universal TM
RR2, RR3
Day 17
Day 18
Day 19
10  More on recursive (decidable) and 
recursively enumerable languages,
Noncomputable languages,
Chomsky hierarchy so far
Review for exam3
 Day 20 (RR4)
Day 21
Day 22
Day 23
  EXAM3 (20 October) 
Time complexity and complexity classes

  • Syllabus is available HERE.
  • Academic calendar for AY2017--2018 is HERE.