Veranstaltungsart: Seminar
Anzeige im Stundenplan: S Formale Sprachen
Modul IP12 (B.Sc.) VL-Nr. 64-172
Semesterwochenstunden: 2 

Unterrichtssprache: Deutsch 

Min. | max. Teilnehmerzahl: - | 20 

Anmeldegruppe: Seminare 
Benutzer und Passwort steht an der Tür zu C-217!


Kommentare/ Inhalte:
Während Grammatiken ein Mittel zur Spezifikation von erlaubten Zeichenketten 
(= formale Sprache) sind, dienen Automatenmodelle zur Analyse oder Transformation. 
Zum Vergleich dieser so unterschiedlich definierten Klassen von formalen Sprachen 
(= Sprachfamilien) benötigt man Klassifikationsverfahren und Kenntnisse über die 
Eigenschaften dieser Sprachfamilien. Zu deren Definition können die unterschiedlichsten 
Methoden eingesetzt werden: 
- Unterschiedliche Regeldefinition und -anwendung bei Grammatiken; 
- Verschiedene Typen von Automaten; 
- Klassifikation aufgrund der Komplexität des Akzeptierens mit Automaten; 
- Operationen, mit denen Sprachen ineinander transformiert werden. 

Besonders dem letzten Aspekt widmet sich die sogenannte AFL-Theory 
(abstract theory of formal languages).

Lernziel:
Kennenlernen des Gebietes, Erlernen der Benutzung theoretisch fundierter Methoden, 
um damit die Ausdruckskraft neuer Konstruktionen in diesem Bereich schnell und sicher 
feststellen zu können. Durch die Erarbeitung von Originalarbeiten aus dem Bereich der 
Formalen Sprachen soll der Umgang mit wissenschaftlicher Literatur eingeübt werden. 
Die Darstellung im Seminarvortrag soll die Kompetenz stärken, Forschungsergebnisse 
mündlich in verständlicher Form darzustellen. Die dazu verwendbaren Techniken sollen 
eingeübt werden.


Vorgehen:
Es stehen mehrere Themen zur Auswahl. Es gibt sowohl einfache Vortragsthemen als als auch 
solche für eher fortgeschrittenere bzw. an Theoretischer Informatik interessierte Studierende.

Je nach Teilnehmerzahl werden einzelne Studierende oder Zweiergruppen Themen aufarbeiten 
und in einem Vortrag präsentieren. Um eine gute Vorbereitung zu gewährleisten, 
haben die Studierenden vor dem eigentlichen Präsentationstermin die Gelegenheit 
zu einer Konsultation mit dem Veranstalter. Es wird nach jedem Vortrag neben einer 
thematischen Diskussion eine zusätzliche Feedback-Runde geben, die sich nur auf den 
Präsentationstil und Ähnliches bezieht. Darüber hinaus soll eine Seminararbeit verfasst werden.

Periodizität: unregelmäßig

Literatur:
Bücher von Harrison, Hopcroft/Ullman, Berstel, Ginsburg, sowie Originalarbeiten von Fischer, 
Greibach, Book u.v. a..

Stichworte: 
Formale Sprachen, Sprachfamilien, Abschlusseigenschaften, rationale Transduktionen, 
Trio-und AFL-Generatoren, schwerste Sprachen, Keller- und Zähler-Automaten, Petrinetzsprachen, 
L-Systeme, Matrixgrammatiken, Chomsky-Hierarchie,

Zusätzliche Hinweise zu Prüfungen:
Stellung im Bachelorstudiengang: 4. Semester oder später, 
FGI-1 sollte erfolgreich abgeschlossen sein!

Stell. im Studienplan des Diplomstudiengangs,  
Hauptstudium, nach auslaufender Studienordnung: 
Block C des Theorie-Profils = individuelles Studienprofil 
entsprechend §7 (4) der Studienordnung und 4. im Rahmenstudienplan für den 
Studiengang Informatik. Nicht nur im Theorie-Profil nutzbar, auch von 
WiInf-Studierenden im Schwerpunkt IM! Voraussetzungen: Grundstudium.