Module Code Semester Type Hours Laboratories / Seminars ECTS Instructors
Introduction to the Theory of Computation ΗΥ025 4 Elective  4
4
Andronikos Th.
Description:
Alphabets and languages. Finite automata. Properties of finite automata and their accepting languages. Regular expressions and regular languages. Equivalence of finite automata and regular expressions. The pumping lemma for regular expressions. Grammars and the Chomsky hierarchy. Context-free languages. Pushdown automata and the pumping lemma for context-free languages. Equivalence of context-free grammars and pushdown automata. The notion of computability. Turing Machines. Decidable and enumerable languages. Church-Turing thesis. Solvable and non-solvable problems. The halting problem. Introduction to computational complexity. Time complexity, the P class, the Cook-Karp thesis. Reduction and completeness. Non-determinism and NP-completeness, P vs. NP. Space complexity, the PSPACE class and PSPACE-complete problems.
Bibliography:
  1. “Introduction to the Theory of Computation”, SIPSER MICHAEL, ITE Publications, ISBN 978-960-524-243-5, 2009 (in greek)
  2. “Elements of the Theory of Computation”Lewis Harry R., Papadimitriou Christos., Kritiki Publications, ISBN 978-960-218-397-7, 2005 (in greek)
Additional Material: