■
Team
■
Teaching
Oberseminar der Theorie
■
Winter 2023
■
Summer 2023
■
Winter 2022
■
Summer 2022
■
Winter 2021
■
Summer 2021
■
Winter 2020
■
Summer 2020
■
Winter 2019
■
Summer 2019
■
Winter 2018
■
Summer 2018
■
Winter 2017
■
Summer 2017
■
Winter 2016
■
Summer 2016
Algorithmik
Ergänzungen zu Mathematik II
Formale Sprachen und Automatentheorie
Konkrete Mathematik
Kryptographische Verfahren
■
Winter 2015
■
Summer 2015
■
Winter 2014
■
Summer 2014
■
Winter 2013
■
Summer 2013
■
Winter 2012
■
Summer 2012
■
Winter 2011
Former Semester
BSc, Master-, Student-, Diplomathesis
StuPro/ ProjektINF/ SoPra/ FaPra
Exam Archive
Standard Textbooks
Descriptive Theory
■
Research
■
Publications
 

Theoretische Grundlagen der Informatik: Formale Sprachen und Automatentheorie

Vorlesung

Prof. Dr. Ulrich Hertrampf

Besondere Ankündigungen

Die Ergebnisse der Scheinklausur stehen im eClaus unter Aufgabenblatt 20 zur Verfügung.

Biergarten-Übung: Am 15. Juli um 17:30 Uhr sind alle FSuA-Übungsteilnehmer eingeladen uns in den Biergarten zu begleiten. Treffpunkt ist der Südausgang des Informatikgebäudes.

Termine

Zeit Raum Termine
Di 15:45-17:00 V47.02 wöchentlich      außer am 14.6. und 21.6.
Do 14:00-15:30 V47.02 wöchentlich      außer am 16.6., 23.6. und 7.7.
 

Folien und voraussichtliche Termine:

Die Einheiten der nächsten Vorlesung sind stets grün unterlegt.

Die zugreifbaren Folien werden entsprechend in der Vorlesung erarbeitet.

Insgesamt wird es 45 Einheiten geben (ohne Einheit 0) - diese werden durchnummeriert von 1 bis 45 und werden im Laufe des Semesters immer rechtzeitig in der folgenden Tafel erscheinen.

Einheit Datum Inhalt Folien
0 05.04. Vorstellung, Arbeitsweise pdf
1 05.04. Sprachen und Grammatiken pdf
2 07.04. Was ist die Chomsky-Hierarchie? pdf
3 07.04. Chomsky-Hierarchie auf Sprachebene pdf
4 07.04. Das Wort-Problem pdf
5 12.04. Syntaxbäume pdf
6 12.04. Mehrdeutigkeit, BNF, Zusammenfassung pdf
7 14.04. Endliche Automaten pdf
8 14.04. DFAs beschreiben Typ-3 Sprachen pdf
9 14.04. Nichtdeterministische Automaten pdf
10 19.04. Der Satz von Rabin und Scott pdf
11 19.04. Typ-3 Sprachen werden durch NFAs erkannt pdf
12 21.04. Reguläre Ausdrücke, Satz von Kleene pdf
13 21.04. Pumping Lemma und sein Beweis pdf
14 21.04. Pumping Lemma: Drei Anwendungen pdf
15 26.04. Der Satz von Myhill und Nerode pdf
16 26.04. Minimalautomaten pdf
17 28.04. Erkennung durch Monoide (Einschub, eine Extrafolie) pdf
18 28.04. Abschlusseigenschaften, Entscheidbarkeitsresultate pdf
19 03.05. Kontextfreie Sprachen, Normalformen (korrigiert) pdf
20 03.05. Chomsky-Normalform: Beweis (korrigiert) pdf
21 10.05. Chomsky-Normalform: Beispiele pdf
22 10.05. Greibach-Normalform: Beweis und Beispiel pdf
23 12.05. Pumping Lemma für Typ-2, mit Beweis pdf
24 12.05. Beispiele, Anwendungen des Pumping Lemmas pdf
25 12.05. Typ-2 und einelementiges Alphabet pdf
26 24.05. Abschlusseigenschaften pdf
27 24.05. Zusammenfassung pdf
28 31.05. Der CYK-Algorithmus, Entwurf pdf
29 31.05. CYK: Programm und Beispiele pdf
30 02.06. Kellerautomaten: Skizze, formale Definition pdf
31 02.06. Konfigurationen und akzeptierte Sprache pdf
32 07.06. Von der Typ-2 Grammatik zum PDA pdf
33 07.06. Vom PDA zur Grammatik pdf
34 09.06. DPDA und DCFL pdf
35 09.06. Abschlusseig. von DCFL, Entscheidbark. bei CFL, DCFL pdf
36 28.06. Typ-1: Kuroda-Normalform, Turingmaschinen pdf
37 28.06. Turingmaschine mit Beschränkung: LBA pdf
38 30.06. Kuroda: Satz und Beweis pdf
39 30.06. Beweis, 2. Richtung pdf
40 05.07. Typ-0 und Typ-1, Satz von Immerman und Scelepcsenyi pdf
41 05.07. Beweis des Satzes (Folie 41.3 korrigiert!) pdf
  07.07. Scheinklausur
42 12.07. Tabellen pdf
43 12.07. Entscheidbarkeiten pdf
44 14.07. Zusammenfassung (1) pdf
45 14.07. Zusammenfassung (2) pdf

Ergänzungen

Martin Seybold, Thomas Mendel

Webseite der Ergänzungen

Übungen

[Jan Philipp Wächter]9/ti/team/waechter/)

Die Anmeldung zu den Übungen erfolgt über https://uebungsgruppen.informatik.uni-stuttgart.de. Benutzername und Passwort werden in der ersten Vorlesung bekannt gegeben.

Weitere Informationen zum Übungsbetrieb finden sich auf Blatt 1.

Übungsgruppen

Hinweis: In der wöchentlich stattfindenden Übungsgruppe 6 werden die Übungen langsamer besprochen.

Gr. Tutor Zeit Raum Besprechung
Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 6
1 T. Böpple Do. 11:30-13:00 0.457 21.04. ∗ ∗ 09.06. 23.06. 07.07.
2 T. Beeh Do. 11:30-13:00 0.463 21.04. ∗ ∗ 09.06. 23.06. 07.07.
3 A. Bühler Do. 15:45-17:15 0.457 21.04. ∗ ∗ 09.06. 23.06. 07.07.
4 J. Welker Do. 15:45-17:15 0.463 21.04. ∗ ∗ 09.06. 23.06. 07.07.
5 F. Weitbrecht Do. 17:30-19:00 0.457 21.04. ∗ ∗ 09.06. 23.06. 07.07.
6 A. Bühler Fr. 08:00-09:30 0.457 22.04.
& 29.04.		 06.05.
& 13.05.		 27.05.
& 03.06.		 10.06.
& 17.06.		 24.06.
& 01.07.		 08.07.
& 15.07.
7 T. Dönicke Fr. 08:00-09:30 0.463 22.04. 06.05. 27.05. 10.06. 24.06. 08.07.
8 V. Klein Fr. 14:00-15:30 0.457 22.04. 06.05. 27.05. 10.06. 24.06. 08.07.
9 D. Tschechlov Fr. 14:00-15:30 0.463 22.04. 06.05. 27.05. 10.06. 24.06. 08.07.
10 D. Tschechlov Fr. 15:45-17:15 0.463 22.04. 06.05. 27.05. 10.06. 24.06. 08.07.
11 T. Böpple Do. 11:30-13:00 0.457 28.04. 12.05. 02.06. 16.06. 30.06. 14.07.
12 T. Beeh Do. 11:30-13:00 0.463 28.04. 12.05. 02.06. 16.06. 30.06. 14.07.
13 A. Bühler Do. 15:45-17:15 0.457 28.04. 12.05. 02.06. 16.06. 30.06. 14.07.
14 J. Welker Do. 15:45-17:15 0.463 28.04. 12.05. 02.06. 16.06. 30.06. 14.07.
15 F. Weitbrecht Do. 17:30-19:00 0.457 28.04. 12.05. 02.06. 16.06. 30.06. 07.07.
16 T. Dönicke Fr. 08:00-09:30 0.463 29.04. 13.05. 03.06. 17.06. 01.07. 15.07.
17 J. Wächter Fr. 14:00-15:30 0.457 29.04. 13.05. 03.06. 17.06. 01.07. 15.07.
18 D. Tschechlov Fr. 14:00-15:30 0.463 29.04. 13.05. 03.06. 17.06. 01.07. 15.07.
19 D. Tschechlov Fr. 15:45-17:15 0.463 29.04. 13.05. 03.06 17.06. 01.07. 15.07.

Änderung:

Am 28.04. findet Übungsgruppe 13 ausnahmsweise in Raum 0.453 statt.

Der Termin zu Blatt 6 für Übungsgruppe 15 findet am 07.07. statt.

∗ Ersatztermine:

Da der 05.05. und der 26.05. Feiertage sind, werden für die Übungen, die regulär an diesen Tagen stattfinden würden, Ersatztermine angeboten. Sollte Ihnen der Besuch des Ersatztermins nicht möglich sein, besuchen Sie eine andere Übungsgruppe und geben Ihrem Tutor Bescheid.

Gr. Tutor Blatt 2 Blatt 3
Datum Zeit Raum Datum Zeit Raum
1 T. Böpple Mi. 11.05. 08:00-09:30 0.124 Mi. 01.06. 08:00-09:30 0.124
2 T. Beeh Fr. 06.05. 17:30-19:00 0.463 Fr. 27.05. 17:30-19:00 0.463
3 A. Bühler Mi. 04.05. 08:00-09:30 0.124 Mi. 25.05. 08:00-09:30 0.124
4 J. Welker Fr. 13.05. 15:45-17:15 0.457 Fr. 03.06. 15:45-17:15 0.457
5 F. Weitbrecht Fr. 06.05. 15:45-17:15 0.457 Fr. 27.05. 15:45-17:15 0.457

Übungsblätter

MC-Blätter

Der letzte MC-Test steht jetzt im eClaus-System unter Blatt 16 bis zum 15.07.16 um 10:00 Uhr zur Bearbeitung bereit.

Die bisherigen MC-Test finden Sie hier als PDF-Dateien:

  • Blatt 11 Hinweis: Bei Teilaufgabe 1 war gemeint, dass Σ die Terminale bezeichnet. Aufgrund des Fehlers wurde die Maximalpunktzahl für diese Teilaufgabe auf 0P geändert.
  • Blatt 12
  • Blatt 13
  • Blatt 14 (geändert: Definition eines Faktors hinzugefügt)
  • Blatt 15
  • Blatt 16 Hinweis: Antwortmöglichkeit 3 von Teilaufgabe 13 war falsch. (Die Aussage gilt für eine Sprache, die einen einzelnen Buchstaben als Wort enthält, nicht.) Aufgrund des Fehlers wurde die Maximalpunktzahl für diese Teilaufgabe auf 0P geändert.

Scheinkriterien

Wer alle der folgenden Bedingungen erfüllt, erhält einen Übungsschein:

  • 50% der maximal erreichbaren Punkte aus den schriftlichen Abgaben
  • 50% der Punkte aus den MC-Tests
  • mindestens zweimal Vorrechnen
  • Bestehen der Scheinklausur (voraussichtlich letzte Semesterwoche)

Hinweis: Um an der Modulprüfung “Theoretische Grundlagen der Informatik” teilzunehmen benötigen Sie einen Übungsschein in “Logik und Diskrete Strukturen” oder in “Formale Sprachen und Automatentheorie”.

Literatur

  • Uwe Schöning: Theoretische Informatik – kurzgefasst, 5. Auflage, Spektrum, 2008. (Die ältere Auflage von 2000 tut’s auch!)
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison-Wesley, 2002.

News

[Jun’23] The paper “Parallel algorithms for power circuits and the word problem of the Baumslag group” by Caroline Mattes and Armin Weiß has been accepted at Computational Complexity.

[Oct’22] The paper “Lower Bounds for Sorting 16, 17, and 18 Elements” by Florian Stober and Armin Weiß has been accepted at ALENEX 2023.

[Sep’22] The paper “Conelikes and Ranker Comparisons” by Viktor Henriksson and Manfred Kufleitner has been accepted at LATIN 2022.

[Sep’22] The paper “Improved Parallel Algorithms for Generalized Baumslag Groups” by Caroline Mattes and Armin Weiß has been accepted at LATIN 2022.

[Apr’22] The paper “Reachability Games and Parity Games” by Volker Diekert and Manfred Kufleitner has been accepted at ICTAC 2022.

[Apr’22] The paper “Satisfiability Problems for Finite Groups” by Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski and Armin Weiß has been accepted at ICALP 2022.

[Mar’22] The paper “The Power Word Problem in Graph Products” by Florian Stober and Armin Weiß was accepted at DLT 2022.

[Nov’20] Volker Diekert is Partner Investigator in the Australian ARC grant “Geodetic groups: foundational problems in algebra and computer science” at University of Technology Sydney.

[Apr’20] The paper “Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems” by Laurent Bartholdi, Michael Figelius, Markus Lohrey and Armin Weiß has been accepted at CCC 2020.

[Apr’20] The paper “Hardness of equations over finite solvable groups under the exponential time hypothesis” by Armin Weiß has been accepted at ICALP 2020.

[Dec’19] The paper “An Automaton Group with PSPACE-Complete Word Problem” by Jan Philipp Wächter and Armin Weiß has been accepted at STACS 2020.

[Nov’19] Carlos Camino was awarded the stuvus Special Prize for exceptional commitment in teaching.

[Jun’19] The paper “The power word problem” by Markus Lohrey and Armin Weiß has been accepted at MFCS 2019.

[May’19] The paper “On the Average Case of MergeInsertion” by Florian Stober and Armin Weiß has been accepted at IWOCA 2019.

[Oct’18] The paper “Worst-Case Efficient Sorting with QuickMergesort” by Stefan Edelkamp and Armin Weiß has been accepted at ALENEX 2019.

[Jun’18] At CCC 2018, Lukas Fleischer received a Best Student Paper Award for his submission “On the Complexity of the Cayley Semigroup Membership Problem”.

[Jun’18] The paper “Testing Simon’s congruence” by Lukas Fleischer and Manfred Kufleitner was accepted at MFCS 2018.

[Jun’18] The paper “The Intersection Problem for Finite Semigroups” by Lukas Fleischer was accepted at DLT 2018.

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.