Topics covered

Fall 2017

1. (Tu, Sep 5)
   • Finite automaton (deterministic)
   • Examples


2. (Tu, Sep 12. )
   • Regular language
   • they are closed under complement, union, intersection, difference
   • Non complete FA and how to make them complete
   • Nondeterministic FA and their equivalence with DFA


3. (Th, Sep 14)
   
• epsilon transitions and how to get rid of them
• Regular languages are closed under concatenation and transitive closure
  


4. (Tu, Sep 19)
   • Equivalence of words (with respect to a language)
   • Minimal automaton for a language
   • The language {ww} is not regular
   • Equivalence of states of a FA
   • How to obtain minimal automaton from an FA
   • Regular expressions

5. (Tu, Sep 26)

• Connection between regular expressions and regular languages
• Pumping lemma and its applications

No class on Th, Sep. 28 (Schönherz Qpa)


6. (Tu, Oct 3)

• Introduction to grammars
  
• Regular grammars
• Connection to regular languages


7.  (Tu, Oct 10)
• Context-free grammars, context-free languages
• epsilon rules can be allowed
  
• chain rules can be avoided


8.  (Th, Oct 12)
• Review


9.  (Tu, Oct 17)
• useless symbols
  
• CF languages are closed under union, concatenation and star


10.   (Tu, Oct  24 )
• Derivation trees
• Pumping lemma for CF languages


11.  (Th, Oct 26)
• Applications of the CF pumping lemma
• CF languages are not closed under intersection and complement
  
• Pushdown automata


12.   (Tu, Oct  31 )
• Examples for pushdown automata
• connection between CF grammars and pushdown automata
13.   (Tu, Nov 7 )
• Deterministic PDAs
• Ambiguous grammars
14.  (Th, Nov 9 )
• Review
15.  (Tu, Nov 14 )
• Turing machines
• Turing-decidable (recursive) and Turing-recognizable )recursively enumerable) languages
•  notion of universal TM
16.  (Tu, Nov 21 )
• Existence of universal TM
• Church-Turing thesis
• The diagonal language is not recognizable
• The universal language is recognizable but not decidable
• The halting problem
17.  (Th, Nov 23 )
• R is the intersection of RE and coRE
  
• Theorem of Rice and some applications
• Post correspondence problem
• Context free ambiguousity is  undecidable
18.   (Tu, Nov 28 )
• time bound, space bound
• TIME, SPACE and their connections
• Time-space theorem
  
• P, PSPACE, EXPTIME