Unit-4 raises some questions about computability. What is computable? What is not computable? What is an intractable problem? What is an NP Complete problem. The travelling salesman problem is a commonly mentioned example of an intractable problem. In addition, we also discuss applications of automata in Lexical Analysis, Parsing and other areas in this unit.
This tutorial on Mathematical Foundations or the Theory of Computation presented in this unit and others are mainly based on Hopcroft, J., Motwani, R. & Ullman, J. (2007), Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison Wesley and Daniel Cohen, (1997), Introduction to Computer Theory, 2nd Edition, John Wiley & Sons, and Sipser, M. (2012) Introduction to the Theory of Computation, Cengage Learning, 3rd edition. Revealing examples are taken from these sources in order to explain mathematical models of computation. Please click here to go back to the Mathematical Foundations home page .
