Prof. Dr. sc. Christoph Meinel
FB IV - Informatik
Die Vorlesung gibt eine kompakte Einführung in das Gebiet der Automatentheorie und formalen Sprachen, das sowohl für die theoretische Informatik (Berechenbarkeitstheorie, Komplexitätstheorie, formale Systeme und Semantik) als auch für die praktische Informatik (Programmiersprachen, Syntaxanalyse, Compilerbau usw.) von grundlegender Bedeutung ist.
Dabei nennen wir eine Menge von Wörtern über einem vorgegebenen Alphabet eine formale Sprache, wenn es ein Regelsystem gibt, das alle Wörter dieser Menge generieren kann (und nur diese). Die Chomsky-Hierarchie teilt die Menge der formalen Sprachen ein in vier Klassen: Die regulären Sprachen, die kontextfreien Sprachen, die kontextsensitiven Sprachen, und schließlich sonstige formale Sprachen. Wir folgen dieser Einteilung und arbeiten für jede dieser vier Klassen die wichtigsten Eigenschaften und Darstellungen heraus. Die Vorlesung gehört zum Kanon der Grundvorlesungen. Die aktive Teilnahme an der angebotenen zweistündigen ist notwendig zum Scheinerwerb.
Die Vorlesung ist 2-stündi
Vorlesung:Übung:
- Do 12-14 ( C9 )
- Do 14-16 ( HS 10)
- Fr 10-12 ( C 22 )
Vorlesungsskript