Formale Sprachen und Automaten

    Vorlesung im Hauptstudium (PG) 3VL+2Ü

    Vorlesung: Prof. Dr. Stephan Braun (UniBW)
    Übungen:   Dr. Thorsten Altenkirch

Termine

Inhalt

Die Vorlesung ergänzt und vertieft den Stoff der Einführungsvorlesung zum Thema "Formale Sprachen und Automaten". In jedem Abschnitt wird zu Beginn an die aus der Einführungsvorlesung bekannten Begriffsbildungen und die wichtigsten Eigenschaften erinnert. Behandelt werden:

1. Varianten endlicher Automaten: Zwei-Wege-Automaten, Automaten mit Ausgabe
2. Schaltwerke: Schaltwerke für Polynome, Schaltwerke für die Codierung
3. Mehrdeutigkeit bei kontextfreien Sprachen: inhärente Mehrdeutigkeit
4. Syntaktische Analyse kontextfreier Sprachen: Lexikalische Analyse, Grundlagen der syntaktischen Analyse, sackgassenfreie Analyse durch Links- und Rechtskontext, Operator- und Präzedenzsprachen, LL-Sprachen, LR-Sprachen
5. Deterministische Kellerautomaten
6. Transition Networks: Selbsteinbettung, Basic Transition Networks
7. Lambda-Kalkül: Informelle Einführung, Formaler Lambda-Kalkül, Normalformen und Konfluenz, Kombinatoren
8. Unentscheidbarkeit: Entscheidbare Sprachen, das Post'sche Korrespondenzproblem, Unentscheidbare Probleme bei kontextfreien Sprachen

Übungsblätter

1. Übungsblatt vom 8.5. - Besprechung am 11.5.
2. Übungsblatt vom 15.5. - Besprechung am 18.5.
3. Übungsblatt vom 22.5. - Besprechung am 25.5.
4. Übungsblatt vom 5.6. - Besprechung am 8.6.
5. Übungsblatt vom 13.6. - Besprechung am 15.6.
6. Übungsblatt vom 26.6. - Besprechung am 29.6.
7. Übungsblatt vom 10.7. - Besprechung am 13.7.
8. Übungsblatt vom 17.7. - Besprechung am 20.7. Beispiellösung zur 3.Aufgabe

Literatur

• J.E.Hopcroft, J.D.Ullman: Introduction to Automata theory, Languages and Computation. Addison-Wesley, 1979.
• A.V.Aho, R.Sethi, J.D.Ullman: Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986
• I.Wegener: Theoretische Informatik. Teubner, 1993