The language was changed to English.

Course Type (SWS)
Lecture: 2 │ Exercise: 2 │ Lab: 0 │ Seminar: 0
Exam Number: ZKD 50036
Type of Lecture:

 Lecture with slides and blackboard

Language: German
Cycle: SS
ECTS: 6
Exam Type

Written exam (120 minutes)

Written Exam (120 min.)
assigned Study Courses
assigned People
assigned Modules
Information
Beschreibung:

Die Theorie der formalen Sprachen bildet die Grundlage für viele andere Gebiete der Informatik, beispielsweise für Informationsverarbeitung, Compilerbau, Verifikation, Modellierung. Im Rahmen dieser Veranstaltung werden die Grundlagen der formalen Sprachen vermittelt und Fertigkeiten im Umgang mit Automaten und Grammatiken eingeübt. Außerdem soll vermittelt werden, in welchen Bereichen diese Theorie zur Anwendung kommt.
Inhalte im Einzelnen:
- Grammatiken, Chomsky-Hierarchie
- Wortproblem, Syntaxbäume
- Reguläre Sprachen (Endliche Automaten, Reguläre Ausdrücke, Pumping-Lemma, Äquivalenzrelationen und Minimalautomaten, Abschlusseigenschaften, Endscheidbarkeit, Anwendung bei Verifikation eines Protokolls zum wechselseitigen Ausschluss)
- Kontextfreie Sprachen (Normalformen, Pumping-Lemma, CYK-Algorithmus, Kellerautomaten, deterministisch kontextfreie Sprachen, Abschlusseigenschaften, Entscheidbarkeit, Anwendung bei XML und DTDs)
- Kontextsensitive und Typ-0-Sprachen, Turing-Maschinen

Lernziele:

Die Studierenden sollen Kenntnisse auf dem Gebiet Automaten und formale Sprachen erwerben. Sie sollen sowohl reguläre, als auch kontextfreie Sprachen und die dazugehörigen Automatenmodelle (endliche Automaten, Kellerautomaten) kennenlernen. Sie sollen selbst in der Lage sein, Automaten und Grammatiken aufzustellen und über ihre Adäquatheit zu argumentieren. Ferner sollen Sie die entsprechenden Algorithmen (Minimierung, CYK, etc.) und Beweismethoden (Pumping-Lemma, etc.) verstehen und anwenden können. Außerdem sollten sie Kenntnisse über Turing-Maschinen und die Grundlagen der Berechenbarkeitstheorie erwerben. Insgesamt sollen sie in die Lage versetzt werden, mit formalen Konzepten umzugehen, selbst formal korrekte Notationen zu verwenden und kleinere Beweise zu führen.

Literatur:

- Uwe Schöning: Theoretische Informatik – kurzgefaßt. Spektrum, 2001
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley/Pearson, 2002

Vorleistung:

Vorlesungen "Grundlagen der Programmiertechnik", "Modellierung"

Infolink:
Bemerkung:
Description:

The theory of formal languages forms the foundation of many other fields of computer science, e.g. information processing, compiler construction, verification, modeling. In this lecture the basics of formal language theory are covered and skills in handling automata and grammars are practiced. Additionally, fields where this theory is applied are considered.
The contents of the lecture in detail:
- Grammars, Chomsky-hierarchy
- Word problem, syntax trees
- Regular languages (finite automata, regular expressions, pumping lemma, equivalence relations and minimal automata, closure properties, decidability, application of regular languages for the verification of protocols for mutual exclusion)
- Context-free languages (normal forms, pumping lemma, CYK-algorithm, push-down automata, deterministic context-free languages, closure properties, decidability, application for XML and DTDs)
- Context sensitive languages and type-0 languages, Turing machines

Learning Targets:

The students should obtain knowledge of automata and formal languages. They should become acquainted with regular as well as context-free languages and the corresponding automaton models (finite automata, push-down automata). They should be able to define automata and grammars and discuss whether they are appropriate. Moreover, the students should understand and use the relevant algorithms (minimization, CYK, and so on) and proof methods (pumping-lemma, and so on). Additionally, they should obtain knowledge about Turing machines and the basics of computability theory. All in all they should be able to handle formal concepts, use formally correct notations on their own and conduct small proofs.

Literature:

- Uwe Schöning: Theoretische Informatik – kurzgefaßt. Spektrum, 2001
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley/Pearson, 2002

Pre-Qualifications:
Info Link:
Notice: