TEACHING 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                                                                                       
     

Teaching Mathematical Foundations Slides (pdf)

Dijkstra's Comments on Mathematical Reasoning

Selected Solutions .

Union & Concatenation of CFLs

[1] Cohen, D. Introduction to Computer Theory. (2nd. Ed.). John Wiley, 1996.
[2] Hopcroft, J., Motwani, R., and Ullman, J. Introduction to Automate Theory, Languages, and Computation. (2nd. Ed) Pearson Education, 2007.
[3] Sipser, M. Introduction to the Theory of Computation, (3rd Ed.) Cengage Learning, 2012.
[4] Rodger, S, H,, . Bressler, B., Finley, T., and Reading, S. Turning automata theory into a hands-on course. In Thirty-seventh SIGCSE Technical Symposium on Computer Science Education, pp. 379-383. SIGCSE, March 2006.