Learning concepts and methods of theoretical computer science, augmenting and deepening the skills acquired in the course "Formale Modellierung". To this aim basic mathematical skills have to be mastered and trained, respectively. (e.g., structural induction, instantiation of abstract concepts in various different examples, using formal languages to specify different forms of information.) Moreover knowledge of important basic results in formal languages as well as propositional and predicate logics is to be achieved.
Specification of of formal languages: regular and context free languages (deepening), Chomsky hierarchy, finite automata (deepening), push-down auomata, Turing machines; elements of complexity theory; syntax-semantic interface, model structures, terms and boolean expressions; classical propositional and first order logic: logical consequence and implication, normal forms.
Not necessary