Formale Sprachen im Sommersemester 2004
Prof. Stephan Braun
Formale Sprachen
3-stündig, Mo 16 - 18 Uhr, Oettingenstr. 67, Oe 1.15, Di 16 - 17 Uhr, Oe .15
Übung 2-stündig, Mi 16 - 18 Uhr, Oettingenstr. 67, Oe 1.15
Aktuelles
- 16.8. Die Ergebnisse der Klausur liegen vor.
- 16.8. Die Scheine werden ausgestellt und unterschrieben. Ab wann sie wo
abgeholt werden können, wird an dieser Stelle bekannt gegeben.
Klausur
Die Klausur wird am 21.7.2004 (Mittwoch) von 16-18 Uhr sein, Dauer 120 Minuten.
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: Endliche Automaten mit Epsilon-Übergängen, Zwei-Wege-Automaten, Automaten mit Ausgabe
- Schaltwerke: Schaltwerke für Polynome
- 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
- Transition Networks: Selbsteinbettung, Basic Transition Networks
- Lambda-Kalkül: Informelle Einführung, Formaler Lambda-Kalkül,
Normalformen und Konfluenz, Kombinatoren
für: Haupt- und Nebenfach Informatik
Vorkenntnisse: Grundkenntnisse in Informatik
Schein: für Diplomprüfung Haupt- und Nebenfach Informatik.
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
- Skript zur Vorlesung, erstellt von Leo Bär im Sommersemester 2002
Ralph Matthes
Last modified: Mon Aug 16 11:16:00 CEST 2004