|
Syllabus |
Historical introduction of the Theory of computation
Theory and practice of regular languages, finite state automata, regular grammars and regular expressions
Theory and practice of algebraic languages, pushdown automata, algebraic grammars.
Turing machines
Other computing models (lambda calculus, kleen recursive functions)
Turing church thesis
Proving the (Un)decidability and (Un)computability
|
|
Main Bibliography |
J.B. Almeida, M.J. Frade, J.S. Pinto, and S. Melo de Sousa. Rigorous Software Development, An Introduction to Program Verification. Springer-Verlag, 307 p. 2011.
A. Arnold and I. Guessarian. Mathematics for Computer Science. Prentice-Hall, 1996.
M. Fernández. Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer, 2009.
Chris Hankin. Lambda Calculi: A Guide for Computer Scientists, volume 3 of Graduate Texts in Computer Science. Clarendon Press, Oxford, 1994.
J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to automata theory, languages, and computation. Pearson education, 2001.
Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1997.
P. Linz. An introduction to formal languages and automata. Jones and Bartlett Publisher, 2006.
Pierre Wolper. Introduction à la Calculabilité. Dunod, PAris, France, 3 edition, 2006.
|