Mathematical Foundations of Computer Science: A Tutorial
Pradip Peter Dey and Hassan Badkoobehi,   National University


Most teachers are deeply interested in structuring the educational environment to maximize student learning outcomes, because they have a genuine interest in creating an engaged learning environment. Mathematical foundations of computer science requires discussion of ideas at a high level of abstraction that may present some challenges to learners because these ideas appear very remote from practical use of computers. Every aspect of computer use is related to mathematical models of computation such as Turing Machines. This tutorial provides a gentle introduction to mathematical models of computation with visual aids.


  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] A Turing Machine for aba*,     [3j] A Turing Machine for binary addition,     [3k] ALAN is NOT computable       [3l] Universal Turing Machine                                                              

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

     

Dijkstra's Comments on Mathematical Reasoning .

Selected Solutions .

Union & Concatenation of CFLs