Qualifikationsziele: Die Studentinnen und Studenten verstehen bei erfolgreichem Abschluss des Moduls die Grundlagen der Beschreibung und syntaktischen Analyse von Programmiersprachen. Sie können formale Sprachen innerhalb der Chomsky-Hierarchie einordnen. Sie beherrschen die gängigen Verfahren um formale Sprachen von einer Beschreibungsform in eine andere zu überführen, sowie Beschreibungen in Normalformen oder minimale Formen zu übersetzen. Aus einer Beschreibung können sie die gemeinte Sprache ableiten. Sie verstehen, dass unterschiedliche Beschreibungsformen von Berechnungsmodellen gleichartig sind und verstehen die Verfahren, um eine Form in die andere zu überführen. Sie verstehen die prinzipiellen Möglichkeiten und Grenzen der Berechenbarkeit. Insbesondere verstehen sie das Halteproblem und seine Unlösbarkeit.

Inhalte: Theoretische Rechenmodelle: Automaten, Turing-Maschinen. Formale Sprachen, Sprachakzeptoren, reguläre Ausdrücke, Grammatiken, Chomsky-Hierarchie, Berechenbarkeit, Komplexität