NumberetiECTS3.0LevelintermediateOverviewThe module introduces the fundamental ideas and problems of the theoretical foundations of computer science.
Formal Languages:
- Repetition: Languages, decision problems, grammars, Chomsky hierarchy
- Finite automata and regular languages, (DFA, NFA and minimal DFA), pumping lemma, proposition of Myhill and Nerode
- Regular expressions
- Context-free languages
Theory of computation:
- Models of computation (Turing machines, recursive functions, loop-, while- und goto-programs)
- Church-Turing thesis
- Decidability and recursive enumerability
- Universal Turing machines
- Undecidability
- Reduction
- Rice’s theorem
Complexity:
- Complexity classes
- Polynomial reduction
- Problems in P and NP
(The order and emphasis of the topics are left to the lecturers.)
Learning objectives- Formal Languages:
Students:
- are able to describe languages with grammars, understand the Chomsky hierarchy and are able to classify languages according to this hierarchy;
- know the properties of regular languages and are able to transform a regular expression to a non-deterministic automaton as well as to a minimal deterministic automaton;
- can, in simple cases, apply the pumping lemma and the proposition of Myhill and Nerode to recognize that a language is not regular;
- are able to bring a context-free grammar to Chomsky normal form and decide the word problem with the Cocke-Younger-Kasami-algorithm.
- Theory of computation:
Students:
- know some important models of computation and are able to explain the Church-Turing thesis.
Students:
- know the notions of decidability and recursive enumerability and understand the concept of a universal Turing machine;
- can explain what an undecidable language is and know some important examples;
- know the notion of reduction, are able to do reductions in simple cases and to explain the Theorem of Rice.
- Complexity:
Students:
- can explain what a complexity class is and know some examples;
- are aware of the importance of the classes P and NP, know important problems in these classes and understand polynomial reduction.
Previous knowledge- Module Mathematics for Computer Science (mgli),
- English level B2 (e.g. passed Module ten1)
Exam formatContinuous assessment grade 
