Formale Sprachen und Automaten
Vorlesung im Hauptstudium (PG) 3VL+2Ü
Vorlesung: Prof. Dr. Stephan Braun (UniBW)
Übungen: Dr. Jan Johannsen
Termine
| VL | Mo, 16-18 | E40, Theresiensstrasse 39 |
| VL | Di, 16-17 | E46, Theresiensstrasse 39 |
| Ü | Mi, 8-10 | 15 |
Die erste Vorlesung findet am 23.4. statt, die erste Übung am 2.5.
Die Klausur findet am Mittwoch, 25.7. zum üblichen Übungstermin statt: 8.30 in Raum 15.
Alle Teilnehmer an der Klausur habe mindestens 50% erreicht und damit
bestanden. Die erreichten Punktzahlen im einzelnen:
| Matrikel-Nr. |
Punkte |
| 011075404863 |
40 |
| 090574304376 |
40 |
| 041278401292 |
40 |
| 031280300079 |
30 |
| 241075305771 |
30 |
| 010278302831 |
38 |
| 270577303051 |
38 |
| 301278300129 |
38 |
| 150278303203 |
40 |
| 190278402883 |
38 |
| 110170309064 |
40 |
Entschuldigung an Konstantin, Markus und Jan, deren richtige
Nichtstandardlösung der Aufgabe 2 ich nicht als richtig
erkannt hatte.
Die Scheine können ab sofort im Sekretariat des Lehrstuhls
(Frau Mignani, Z1.05) abgeholt werden.
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:
- Varianten endlicher Automaten:
Zwei-Wege-Automaten, Automaten mit Ausgabe
- Schaltwerke:
Schaltwerke für Polynome, Schaltwerke für die
Codierung
- Mehrdeutigkeit bei kontextfreien Sprachen: inhärente
Mehrdeutigkeit
- Syntaktische Analyse kontextfreier Sprachen:
Lexikalische Analyse, Grundlagen der syntaktischen Analyse,
sackgassenfreie Analyse durch Links- und Rechtskontext,
Operator- und Präzedenzsprachen, LL-Sprachen, LR-Sprachen
- Deterministische Kellerautomaten
- Lambda-Kalkül:
Informelle Einführung, Formaler Lambda-Kalkül,
Normalformen und Konfluenz, Kombinatoren
- Unentscheidbarkeit:
Entscheidbare Sprachen, das Post'sche Korrespondenzproblem,
Unentscheidbare Probleme bei kontextfreien Sprachen
- Grundzüge der Komplexitätstheorie:
Komplexitätsklassen, praktisch unlösbare Probleme
Übungsblätter
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
Jan Johannsen
Last modified: Mon Jul 2 10:02:46 CEST 2001