Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage, die Sprachklassen der Chomsky-Hierarchie zu definieren, Beispiele aus diesen Sprachklassen anzugeben sowie vorgegebene Beispiele zu lösen. Im Bereich der Logik sind Studierende in der Lage, Modelle und Gegenbeispiele zu gegebenen prädikatenlogischen Formeln zu finden sowie die Grundlagen von Hilbert- und Tableau-Kalkül zu erläutern und einfache vorgegebene Beispiele in diesen Kalkülen zu lösen.
Spezifikation formaler Sprachen: reguläre und kontextfreie Sprachen (vertiefend), Chomsky-Hierarchie, endliche Automaten (vertiefend), Kellerautomaten, Turingmaschinen, Elemente der Komplexitätstheorie; Syntax-Sematik-Schnittstelle, Modellstrukturen, Terme und Boolesche Ausdrücke; ausgewählte Kapitel der klassischen Aussagen- und Prädikatenlogik, Hilbert- und Tableaux-Kalkül.
Vortrag der wichtigsten Inhalte und Vorrechnen von Beispielen.
2 Übungsblätter, die vor der mündlichen Abschlussprüfung zu erarbeiten sind.
Mündliche Abschlussprüfung.
Nicht erforderlich