1 Time and place:

Thursday, 16:15–18:00, HS 11, beginning 9.3.2017

2 Prerequisites:

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).

3 Course desription and contents:

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):

• Showing the equivalence of the two above characterizations for each class, and of other characterizations not mentioned at this place.
• Methods for showing that a given language does not belong to a particular class.
• Closure properties, for instance: does the union, intersection etc. of two languages in a class C again belong to C?
• Some further classes languages, related to the ones above, leading to a refinement of the Chomsky hierarchy.
• Are there algorithms for various decisions problems about formal languages, for instance, for deciding if L₁ ⊆ L₂ for given languages L₁, L₂ in one of the above classes?

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.

4 Literature:

Lecture notes will be handed out.

5 Assessment:

A written or oral exam after the course.