Contents
The aim of this course is to provide the participants with basic knowledge of the foundation computer science.
Headlines:
Formal languages and automata. Regular languages and their formalisms: finite automata, regular expressions and grammars. Context-free languages: push-down automata, grammars and parsing. Standard examples of results and techniques: relating the expressive power of formalisms (Kleene's Theorem), minimization of automata, closure properties, pumping lemmas, etc.
Computability. Universal computational models (incl Turing Machines). Undecidable problems, diagonalization. Reduction techniques, and examples of undecidable problems in different domain areas (grammars, tiling).
Text-books
Will be announced
Evaluation
Oral examination
ECTS-credits:
10
Semester
Spring