Formale Sprachen und Automaten

    Vorlesung im Hauptstudium (PG) 3VL+2Ü

    Vorlesung: Prof. Dr. Stephan Braun (UniBW)
    Übungen:   Martin Lange
    

Termine

Alle Teilnehmer an der Klausur haben mindestens 50% erreicht und damit bestanden. Die erreichten Punktzahlen im einzelnen:

Matrikel-Nr.	Aufgabe 1	Aufgabe 2	Aufgabe 3	Punkte gesamt
090979401351	10	10	8	28
080978301619	10	10	7	27
070273306598	10	10	2	22
051175304140	8	7	5	20
070478401593	10	6	3	19
010175304971	9	7	2	18
181175303923	9	8	1	18
200575304127	9	4	5	18
250580401266	7	8	3	18

Die Klausur kann ab sofort in Raum D1.07, Oettingenstrasse 67, eingesehen und abgeholt werden. Die Scheine sind in Bearbeitung und sind ab dem 26.8.2002 ebenfalls in Raum D1.07 erhältlich.

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. Lambda-Kalkül: Informelle Einführung, Formaler Lambda-Kalkül, Normalformen und Konfluenz, Kombinatoren
7. Unentscheidbarkeit: Entscheidbare Sprachen, das Post'sche Korrespondenzproblem, Unentscheidbare Probleme bei kontextfreien Sprachen
8. Grundzüge der Komplexitätstheorie: Komplexitätsklassen, praktisch unlösbare Probleme

Skript zur Vorlesung, Dank an Leo Bär: Teil 1, Teil 2.

Übungsblätter

• Blatt 6 (10.6.2002)
• Blatt 7 (17.6.2002)
• Blatt 8 (24.6.2002)
• Blatt 9 (1.7.2002)
• Blatt 10 (9.7.2002)

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