Class Description

Course_ID: MYY501

Weekly Hours: 5

Semester: 5

ECTS Credits: 6

Course Homepage:http://www.cse.uoi.gr/~palios/automata/

Description: Finite automata and regular expressions, regular languages, closure properties, pumping lemma, algorithms. Determinism, non-determinism. Pushdown automata and context-free grammars, context-free languages, closure properties, pumping lemma, algorithms. Chomsky normal form. Turing machines, equivalence of different models. Recursive and recursively enumerable languages. Church-Turing thesis. Undecidability, the halting problem, Post’s correspondence problem. Classes P and NP.