Course details
Theoretical Computer Science
Guarantor
Language of instruction
Czech
Completion
Credit+Examination
Time span
- 39 hrs lectures
- 13 hrs projects
Department
Syllabus of lectures
- An overview of the applications of the formal language theory, the modelling and decision power of formalisms, operations over languages.
- Regular languages and their properties, Kleene's theorem, Nerod's theorem, Pumping lemma.
- Minimalization of finite-state automata, the relation of indistinguishability of automata states, construction of a reduced finite-state automaton.
- Closure properties of regular languages, regular languages as a Boolean algebra, decidable problems of regular languages.
- Context-free languages and their properties, normal forms of context-free grammars, unambiguous and deterministic context-free languages, Pumping lemma for context-free languages.
- Closure properties of context-free languages, closedness wrt. substitution and its consequences, decidable problems of context-free languages.
- Turing machines (TMs), the language accepted by a TM, recursively enumerable and recursive languages and problems, TMs and functions, methods of constructing TMs.
- Modifications of TMs, TMs with a tape infinite on both sides, with more tapes, nondeterministic TMs, automata with two push-down stacks, automata with counters.
- TMs and type-0 languages, diagonalisation, properties of recursively enumerable and recursive languages, linearly bounded automata and type-1 languages.
- Computable functions, initial functions, primitive recursive functions, mu-recursive functions, the relation of TMs and computable functions.
- The Church-Turing thesis, universal TMs, undecidability, the halting problem, reductions, the Post's correspondence problem.
- Undecidable problems of the formal language theory.
- An introduction to the computational complexity, Turing complexity, the P and NP classes and beyond.
Course inclusion in study plans