Introduction to the Theory of Computation

This course aims to introduce students to the concept of computation and the basic models of computation.

Upon successful completion of this course, the students will be able to:

• Understand in depth the concept of computation and computability.
• Familiarize themselves with the simplest models of computation, such as finite automata (deterministic and nondeterministic) and pushdown automata.
• Become acquainted grammars and, particularly, context-free grammars.
• Make a first foray into Turing Machines and complexity classes such as P, ΝΡ, PSPACE, and the notion of NP-completeness.

This course is an introductory course to the Theory of Computation for second year undergraduate students. It covers the following topics:

• 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.

1. “Εισαγωγή στη Θεωρία Υπολογισμού”, Sipser Michael, Εκδόσεις ΙΤΕ-Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-558-0, 2019
2. “Στοιχεία θεωρίας υπολογισμού”, Lewis Harry R., Παπαδημητρίου Χρίστος Χ., Εκδόσεις Κριτική ΑΕ, ISBN 978-960-218-397-7, 2005