Automatentheorie, Formale Sprachen und Berechenbarkeit (AUFS)

Belegbar Sommersemester, Wintersemester
ECTS-Punkte 10 (ca. 300 Stunden)
Fachgebiet Theoretische Informatik

Ziel des Moduls

Stellen Sie sich vor, Sie haben die Aufgabe einen Fahrkartenautomaten zu realisieren, ein Bestellformular für eine E-Commerce-Anwendung festzulegen oder Geschäftsabläufe in Ihrem Unternehmen zu beschreiben.

Wie gehen Sie vor? Sicher setzen Sie sich nicht gleich an den Rechner und implementieren die Software mit einem Werkzeug wie C++, Java oder HTML – mit der Folge, dass Ihre Systemlösung vom Werkzeug abhängt und bei Versionen-, Release- oder Systemwechseln unbrauchbar wird.

In diesem Modul lernen Sie zeitinvariante Methoden, Techniken und Werkzeuge für die Entwicklung von Systemen kennen, mit deren Hilfe Sie effektiv und systematisch an Problemlösungen mitarbeiten können. Der Einsatz der formalen Konzepte wird anhand von vielen Beispielen motiviert und ausprobiert.

Inhalt des Moduls
  • Endliche Automaten und reguläre Sprachen
  • Kontextfreie Sprachen und Kellerautomaten
  • Berechenbarkeit und Komplexität
Inhalt im Detail

Teil 1: Endliche Automaten und reguläre Sprachen

  • Deterministische endliche Automaten
  • Nichtdeterministische endliche Automaten
  • Endliche Automaten mit ε-Übergängen
  • Minimale endliche Automaten
  • Anwendungen endlicher Automaten
  • Reguläre Ausdrücke
  • Typ-3-Grammatiken
  • Eigenschaften regulärer Sprachen
  • Endliche Maschinen

Teil 2: Kontextfreie Sprachen und Kellerautomaten

  • Kontextfreie Grammatiken
  • Kellerautomaten
  • Anwendungen kontextfreier Sprachen

Teil 3: Berechenbarkeit und Komplexität

  • Typ-1- und Typ-0-Sprachen
  • Turingautomaten
  • Berechenbarkeit
  • Entscheidbarkeit
  • Komplexität
Umfang des Moduls
  • Lehrbuch der Theoretischen Informatik
  • Begleittext, der zum Studium des Lehrbuchs anleitet
  • Übungsaufgaben
  • Studienbegleitendes Tutorium
Empfohlene Vorkenntnisse

Mathematische Grundkenntnisse über die Begriffe "Menge", "Relation" und "Funktion" in einem Umfang und einer Tiefe, wie sie der Vorkurs Mathematik vermittelt. Fähigkeit zum abstrakten Denken.

Herausgeber und Autor

Prof. Dr. Kurt-Ulrich Witt
Hochschule Bonn-Rhein Sieg, St. Augustin

Kursdauer
1 Semester

Kosten
zur Kostenübersicht Einzelmodule

Abschluss
Das Modul ist verwendbar für die Abschlüsse: