Thursday, 16:15–18:00, HS 11, beginning 9.3.2017
Students should be familiar with the most basic notions of set theory (unions, intersections, power set etc.) and with the most basic proof methods (like induction).
There are four classes of languages which make up the Chomsky hierarchy, namely the classes of regular, context-free, context-sensitive and recursively enumerable languages. Their investigation is one of the classical topics of theoretical computer science, and it is also motivated by various applications, notably in the realm of compiler design. Each of the four classes can be characterized by one particular type of automaton (abstract computing devices), capable of accepting languages in the class considered, or by one particular type of grammar, allowing a formal description of such languages. For instance, any recursively enumerable language can be accepted by a Turing machine or described by an unrestricted grammar. The following issues will be dealt with (without presenting all proofs):
Turing machines are actually capable of performing any algorithm, so an investigation of their limitations leads to undecidable (algorithmically unsolvable) problems. A few undecidability results will be derived in the course.
Lecture notes will be handed out.
A written or oral exam after the course.