Mathematical Foundations: Computer Theory, Complexity, Automata & Languages
Dr. Pradip Peter Dey,     National University

Course Description: A study of mathematical models of computation and theoretical foundations of computer science. Proof techniques, automata theory, Chomsky hierarchy, decidability and computational complexity are emphasized.
Course Outline
Course Learning Outcomes: See Course Outline
WEB-BASED LECTURE NOTES:


  UNIT_1:    
[1a] Introduction,     [1b] Finite Automata,    [1c] Regular Languages,    [1d] Regular Languages in MS Word format,     [1e] Animation of a Finite Automaton,     [1f] Chomsky Hierarchy,
  [1g] DFA NFA                                                             

    UNIT_2:    
[2a] Context-Free Grammars,     [2b] Context-Free Grammars in Word format,    [2c] Context-Free Grammar Slides,     [2d] Context-Free Grammar Slides in PowerPoint,     [2e] One-Stack Automata,      [2f] One-Stack Automata in Word format    [2g] Animation of One-Stack Automata,     [2h] Context-Free Languages,     [2i] Context-Free Languages in Word format    [2j] Pushdown Automata,    [2k] Animation of Pushdown Automata,    [2l] Pumping Lemma for CFLs

  UNIT_3:   
[3a] Turing Machines,     [3b] Turing Machines in Word format     [3c] Animation of Turing Machines,     [3d] Coding Turing Machines,       [3e] Post Machines,     [3f] HRU Model for Secueity     [3g] Turing Machine Languages in pdf     [3h] Turing Machine Languages,     [3i] Animation of a Turing Machine for aba*,     [3j] A Turing Machine for binary addition,     [3k] ALAN is NOT computable                                                                  

  UNIT_4:    
[4a]What is not computable?    [4b] The Halting Problem,     [4c] Intractable Problems,     [4d] Applications in other areas,     [4e] Chomsky Hierarchy,     [4f] New Models of Computation                                                                                       

Project Options & Extra Credit Assignments      

Dijkstra's Comments on Mathematical Reasoning .

Additional Course Information

Selected Solutions .

A repeatable Optional Quiz .

Union & Concatenation of CFLs