**Course Contents (Syllabus):**

Finite automata and regular expressions. Pushdown automata and context-free grammars. Turing machines and Church's thesis. Undecidability. Computational complexity.

Elective course, 4th year**Prerequisites and/or related courses: **

Discrete Mathematics, Introduction to Programming, Object-oriented Programming, Algorithms and Complexity, Graph Theory**Objectives:**

- Automata and formal grammars

- Turing Machines- Determinism vs non-determinism

- Unsolvability

- Polynomial hierarchy

- P vs NP**Teaching Methods:**

Theory lectures (4h/week) and additionally seminars (2h/ 3 weeks) solving exercises.

**Assessment methods:**

One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.

**Teaching Material:**Notes

**Recommended reading:**

- M. Sipser, ‘’Introduction to Theory of Computation’’, Panepistimiakes Ekdosis Kritis, 2007 (in Greek).

- H. R. Lewis & Ch. Papadimitriou, ‘’ Elements of Computation’’, Kritiki, 2005 (in Greek).**Bibliography:**

- M. Sipser, ‘’Introduction to Theory of Computation’’, Panepistimiakes Ekdosis Kritis, 2007 (in Greek).

- H. R. Lewis & Ch. Papadimitriou, ‘’ Elements of Computation’’, Kritiki, 2005 (in Greek).

- E. Zachos, ‘’Automata and Formal Grammars’’, Notes, National Technical University of Athens, 2008 (in Greek).

- E. Zachos, ‘’Computability and Complexity’’, Notes, National Technical University of Athens, 2004 (in Greek).