Spezialvorlesung Logik und Softwaredesign: Formale Sprachen und formale Grammatiken

Dr. Heinrich Rolletschek

February 16, 2017

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

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.