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.
Processing Context-Free Languages with One-Stack Automata
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                                                             
    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,     [3h] Animation of a Turing Machine for aba*,     [3i] A Turing Machine for binary addition                                                                      
  UNIT_4:    
[4a]What is not computable?    [4b] The Halting Problem     [4c] Intractable Problems     [4d] Applications in other areas, [4e] Chomsky Hierarchy                                                                                      
Project Options & Extra Credit Assignments      

Dijkstra's Comments on Mathematical Reasoning .

Additional Course Information

Selected Solutions .

A repeatable Optional Quiz .

Union & Concatenation of CFLs