Lehrveranstaltung:
Formale Sprachen und Grammatiken I + II
Veranstaltungsform:
V+Ü (3+1) und V+Ü (4+2)
jeweils aufeinanderfolgend
Inhalt:
Im Zentrum der Vorlesung stehen Fragestellungen, die in natürlichem
Zusammenhang mit der Beschreibung, der syntaktischen Analyse sowie der
Übersetzung von Programmiersprachen stehen.
Dabei dient Teil I vorwiegend der Darstellung allgemeiner Grundlagen,
die in Teil II in Hinblick auf die Syntaxanalyse kontextfreier Sprachen
vertieft werden.
Teil I
- die Chomsky Hierarchie
- Akzeptoren
- Abschlußeigenschaften
- Nichtentscheidbarkeit
- Eindeutigkeit und Mehrdeutigkeit
Teil II
- Greibachnormalform und Greibachsprache
- allgemeine Sytaxanalyseverfahren für kontextfreie Sprachen
- Syntaxanalyse deterministischer kontextfreier Sprachen
(u.a. LR(k)-Verfahren)
Literatur:
M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley 1978
J.E. Hopcroft, J.D. Ullman, Intoduction to Automata Theory, Languages and
Computations, Addison- Wesley 1979 (die deutsche Übersetzung ist nicht
zu empfehlen)
Einordnung in Studienplan und Prüfungsordnung:
Informatiker, Mathematiker mit Schwerpunkt Informatik, Technische Informatik
(Datentechnik), Aufbaustudium Informatik
Voraussetzungen: Einschlägige Vordiplome
Weitere Veranstaltungen, die ein sinnvolles Prüfungsfach ergeben :
Endliche Automaten I+II, Algebraische Kodierungstheorie,
Abstrakte Datentypen