Automatentheorie und formale Sprachen (AFS)

Ein Blick hinter die Logik von Software: Du lernst, wie Programme strukturiert sind, entwickelst eigene Modelle und nutzt diese, um komplexe Rechen- und Softwareprobleme zu lösen.

Inhalte

• In der Veranstaltung soll eine Einführung in die Automatentheorie und die Theorie der formalen Sprachen gegeben werden. Mit dem Begriff Automatentheorie ist das Studium abstrakter Rechengeräte gemeint. Als es noch keine Computer gab entwickelte Alan Turing eine abstrakte Maschine, die über sämtliche Fähigkeiten heutiger Computer verfügte. Ziel war es zu differenzieren zwischen dem, was eine Maschine berechnen kann und dem, was sie nicht berechnen kann. In den 40er und 50er Jahren wurden dann einfachere Maschinen untersucht, die heute als endliche Automaten bezeichnet werden und sich für verschiedene Zwecke als außerordentlich nützlich erwiesen haben. Zudem begann der Linguist Chomsky, formale Grammatiken zu untersuchen, die eine enge Verwandschaft zu abstrakten Automaten aufweisen. Einige dieser Konzepte wie endliche Automaten und bestimmte Arten formaler Grammatiken werden heute im Design und im Aufbau wichtiger Arten von Software verwendet. Neben Beweistechniken werden wir die Grundlagen der Automatentheorie und der formalen Sprachen legen und an Beispielen erörtern. Unter anderem werden deterministische und nicht-deterministische endliche Automaten, Push down Automaten, reguläre Ausdrücke und Sprachen, kontextfreie und kontextsensitive sowie Turing erkennbare und Turing entscheidbare Sprachen besprochen.

Lernziele/Kompetenzen

• die Grundlagen der Automatentheorie und der formalen Sprachen zu beschreiben.
• zu gegebenen Automaten/Grammatiken die passende Sprache zu erkennen sowie zu einer Sprache einen Automaten/eine Grammatik zu definieren.
• die verschiedenen Arten von endlichen Automaten sowie formalen Sprachen zu beschreiben und sie beherrschen deren Eigenschaften sowie entsprechende Algorithmen zur Umwandlung.

Literatur

• Folgende Bücher können ergänzend zur Veranstaltugn gelesen werden:
• Schöning: Theoretische Informatik – kurzgefaßt. Spektrum, 2008. (5. Auflage)
• Hollas, Boris: Grundkurs Theoretische Informatik, Spektrum Akademischer Verlag 2007
• Rich: Automata, Computability, and Complexity, Pearson 2008
• Asteroth, Baier: Theoretische Informatik, Pearson, 2003.
• Vossen, Witt: Grundkurs Theoretische Informatik, vieweg, 2006.

Dozentinnen / Dozenten

• Prof. Dr. Lutz Strüngmann

Empfohlene Vorkenntnisse

• keine

Daten zum Modul

Semesterwochenstunden

Arbeitsaufwand (work load)