Universität Leipzig    Institut für Informatik    Automaten und Sprachen    Karin Quaas
Sommersemester 2014 Bachelorseminar Automatentheorie
	Thematisch setzen wir uns dieses Semester mit dem Bau von Compilern auseinander. Dazu lesen wir das Standardwerk von Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers: Principles, Techniques and Tools - Red Dragon Book, welches Sie hier herunterladen können. Das Seminar wird in Form einer Lesegruppe (Reading group) stattfinden. Dabei werden wir einen vorgegeben Text selbständig lesen und gemeinsam in der wöchentlich stattfindenden Sitzung diskutieren. Die Seminarteilnehmer stimmen zu, sich gemäß zuvor festgelegten Seminarregeln zu verhalten. Das Seminar findet im Rahmen des Seminarmoduls 10-201-2116, Theoretische Informatik, statt. Grundkenntnisse zu Formale Sprachen, Logik, Endliche Automaten, Progammierung (Grundstudium) sind erforderlich.
Termine
	Mittwochs, 9:15-10:45, Paulinum P-801
	Achtung! Änderung auf Mittwochs, 11:15-12:45, SG 311, ab 11.06.2014
	Sprechzeiten: Bei Fragen oder Problemen können Sie mir eine Email schreiben oder Mittwochs zwischen 10:45 und 11:10 in meinem Büro vorbeischauen.
Seminarregeln
	Von den Teilnehmern wird erwartet, dass sie sich aktiv mit dem Seminarthema auseinandersetzen und eigenständige Darstellungen erarbeiten. Eine Seminarsitzung wird eröffnet durch ein äußerst kurzes Statement (ca. 5 Minuten) über den Inhalt des in der vorherigen Woche festgelegten Lesestoffs. Der Berichterstatter wird nach einem Losverfahren in der aktuellen Sitzung bestimmt. Die Diskussion des Lesestoffs erfolgt nach den Regeln der herrschaftsfreien Kommunikation (keine Worterteilung oder sonstige autoritäre Lenkung der Diskussion). Sollte die Gruppe es wünschen, kann zeitweise eine Moderation durch einen Seminarteilnehmer erfolgen. Erfolgreicher Abschluss des Seminars durch Bonus-Malus-Punkte-System: Voraussetzung für erfolgreichen Abschluss des Seminars sind 4 Pluspunkte am Ende des Seminars Ausschluss aus dem Seminar sobald man 4 Minuspunkte erreicht hat Punkte können nach folgenden Kriterien auf das persönliche Konto eines jeden Seminarteilnehmers gutgeschrieben werden: 1 Plus- bzw. 1 Minuspunkt bei erfolgtem bzw. unentschuldigtem nicht erfolgtem mündlichen Statement zu Beginn der Sitzung. 1 Pluspunkt für die Moderation einer Sitzung. 2 Pluspunkte für eine mündliche Darstellung eines Problems (ca. 15 Minuten). 4 Pluspunkte für eine schriftliche Problembearbeitung. 1 Minuspunkt bei unbegründetem/unentschuldigtem Fehlen. Als Entschuldigung gilt die Angabe von Gründen ohne weiteren Beleg.
Sitzungen
	1. Sitzung: Annahme der Seminarregeln, Festlegung Lesestoff: 1.1, 1.2, 1.4., 2.1, 2.2, inklusive Aufgaben
	2. Sitzung: Statement von Hydra; Compiler, Interpretierer, Assembler; Tokens: mit oder ohne Attributwerte (unklar!); Unentscheidbarkeit und Halteproblem; Festgelegter Lesestoff: 2.1, 2.2, 2.3
	3. Sitzung: Statement von Phönix, Protokoll von Hydra; CFGs, Parsing, Mehrdeutigkeit, Syntax-directed translation, Translation Schemes; Festgelegter Lesestoff: 2.4
	4. Sitzung: fehlendes Statement von Dragodon, Statement von Phönix, Kapitel 2.4: Parsing, CFG Römische Zahlen, Festgelegter Lesestoff: 2.5, 2.6. Aufgabe 2.2.5 (!)
	5. Sitzung: Statement von Basilisk, Moderation von Hydra
	6. Sitzung: Statement von Hydra, Lexikalische Analyse, Scanning, Lexeme, Tokens, Reguläre Ausdrücke und reguläre Definitionen, Chomsky Hierarchie, Neuer Lesestoff: 3.4,3.5,3.6, Aufgaben: Beweis 3.3.2, Aho-Corsick-Algorithmus nach 3.4.2
	7. Sitzung: Wiederholung Chomsky Hierarchie und nicht-semientscheidbare Sprachen, Kapitel 3.4, Lex: Werkzeug zur Generierung eines lexikalischen Analyzers, Lex und Pig Latin; bis zur nächsten Sitzung: Beweis 3.3.2 schriftlich als Möglichkeit einen Pluspunkt zu erhalten, Aho-Corsick-Algorithmus nach 3.4.2, bis Ende des 3. Kapitels
	8 Sitzung: Statement von Basilisk, Simulierung von DFA versus Simulierung von NFA, Umwandlung eines NFAs in einen äquivalenten DFA, Umwandlung eines regulären Ausdrucks direkt in einen DFA via nullable, lastpos, firstpos, und followpos, Lesestoff bis nächste Woche: 4.1 und 4.2
	9 Sitzung: Statement von Phönix, Syntaxbaum vs. Parsebaum, Kapitel 4.1, 4.2 besprochen, keine Probleme darin, Aufgabe 4.2.8 b steht zur Einholung von Punkten offen, bis nächste Woche: bis S. 231.
	10. Sitzung: Festlegung neuer Lesestoff: 4.5.
Punktestand
Name Punkte Hydra 4 Krypdis 0 Phönix 3 Dragodon -4 Basilisk 2