Automaten und formale Sprachen
Automata and Formal Languages

Modul IN2041

Dieses Modul wird durch Fakultät für Informatik bereitgestellt.

Diese Modulbeschreibung enthält neben den eigentlichen Beschreibungen der Inhalte, Lernergebnisse, Lehr- und Lernmethoden und Prüfungsformen auch Verweise auf die aktuellen Lehrveranstaltungen und Termine für die Modulprüfung in den jeweiligen Abschnitten.

Modulversion vom WS 2015/6 (aktuell)

Von dieser Modulbeschreibung gibt es historische Versionen. Eine Modulbeschreibung ist immer so lange gültig, bis sie von einer neuen abgelöst wird.

verfügbare Modulversionen
WS 2015/6WS 2011/2

Basisdaten

IN2041 ist ein Semestermodul in Englisch auf Bachelor-Niveau und Master-Niveau das im Wintersemester angeboten wird.

Das Modul ist Bestandteil der folgenden Kataloge in den Studienangeboten der Physik.

  • Allgemeiner Katalog der nichtphysikalischen Wahlfächer
GesamtaufwandPräsenzveranstaltungenUmfang (ECTS)
240 h 90 h 8 CP

Inhalte, Lernergebnisse und Voraussetzungen

Inhalt

The module is divided into two parts. The first part deepens and expands the study of finite automata initiated in IN0011 (Introduction to theoretical computer science), while the second introduces automata on infinite words. In both parts automata are seen as a data structure for the manipulation of (possibly infinite) sets and relations. The module shows how to implement Boolean operations and joins for different automata classes (nondeterministic and deterministic automata, binary decision diagrams, Büchi automata). It also introduces the connection between automata and logic. The algorithms are applied to a variety of problems, ranging from pattern-matching to program verification and solution of Diophantine equations.

Lernergebnisse

On successful completion of the module, students will be able to
- use finite automata as a data structure for representation of finite and infinite sets;
- understand and determine the computational complexity of different operations for different classes of automata;
- move to and fro logical and automata-theoretic descriptions;
- apply automata to problems in pattern matching and formal verification.

Voraussetzungen

IN0011 Einführung in die Theoretische Informatik

Lehrveranstaltungen, Lern- und Lehrmethoden und Literaturhinweise

Lehrveranstaltungen und Termine

ArtSWSTitelDozent(en)Termine
VU 6 Automata and Formal Languages (IN2041) Esparza Estaun, F. Mo, 10:00–12:00, 5613.02.010
Do, 14:00–16:00, 5613.02.010

Lern- und Lehrmethoden

The module consists of lectures and tutorials. During the lectures students are asked to solve small exercises online. Students also received weekly assignments, whose solution is discussed in the tutorials.

Medienformen

Slide show, blackboard, tool presentations, written assignments.

Literatur

Javier Esparza: Automata Theory --- An algorithmic approach. Lecture notes, 2012.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman; Introduction to Automata Theory, Languages and Computation; Addison-Wesley Longman, 3rd edition, 2006.
Joerg Flum, Erich Graedel, Thomas Wilke (eds.); Logic and Automata: History and Perspectives, Volume 2; Amsterdam University Press, 2008.
Dominique Perrin, Jean-Eric Pin; Infinite Words: Automata, Semigroups, Logic and Games; Academic Press, 2004.

Modulprüfung

Beschreibung der Prüfungs- und Studienleistungen

Die Studierenden werden mittels einer schriftlichen Prüfung von 120 Minuten bewertet.
Ein Teil der Prüfungsaufgaben überprüft, ob der Studierende endliche Automaten entweder direkt oder mit Hilfe der entsprechenden Algorithmen zur Komposition von endlichen Automaten konstruieren kann.
Ein weiterer Teil der Aufgaben überprüft, ob der Studierende dazu in der Lage ist, die in der Vorlesung behandelten Verfahren zum Wechsel zwischen logischer oder automatentheoretischer Beschreibung anzuwenden und zu kombinieren. Schließlich wird noch überprüft, ob der Studierende die richtigen automatentheoretischen Techniken auswählen kann, um Probleme aus dem Bereich der Verifikation und des Pattern-Matchings zu lösen.

Wiederholbarkeit

Eine Wiederholungsmöglichkeit wird am Semesterende angeboten.

Kondensierte Materie

Wenn Atome sich zusammen tun, wird es interessant: Grundlagenforschung an Festkörperelementen, Nanostrukturen und neuen Materialien mit überraschenden Eigenschaften treffen auf innovative Anwendungen.

Kern-, Teilchen-, Astrophysik

Ziel der Forschung ist das Verständnis unserer Welt auf subatomarem Niveau, von den Atomkernen im Zentrum der Atome bis hin zu den elementarsten Bausteinen unserer Welt.

Biophysik

Biologische Systeme, vom Protein bis hin zu lebenden Zellen und deren Verbänden, gehorchen physikalischen Prinzipien. Unser Forschungsbereich Biophysik ist deutschlandweit einer der größten Zusammenschlüsse in diesem Bereich.