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

- 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
_{1} ⊆ L_{2} for given languages L_{1}, L_{2}
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.