Automaten und Berechenbarkeit

Sommersemester 2019

Vorlesung: Prof. Dr. habil. Klaus Reinhardt

Übungen: Dr. Renate Winter

Vorlesung:

Literatur:

I. Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 2. Auflage 1999, Teubner, Stuttgart. ISBN 3-5191-2123-9

J. Hopcroft, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 3. Auflage 1994, 461 Seiten, kart., Addison Wesley, Bonn. ISBN 3-89319-744-3

J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Berechenbarkeit, 3. Auflage 2011, Pearson Studium, München. ISBN 978-3-86894-082-4

J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory, Languages, an Computation, 2001, Addison-Wesley. ISBN 0-201-44124-1

Garey, Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. ISBN 0-7167-1044-7

K. W. Wagner: Lehrbuch der Theoretischen Informatik, Springer-Verlag Berlin 1994, 2003. ISBN 3-540-58139-1

R. Winter: Theoretische Informatik, Oldenbourg-Verlag München 2002. ISBN 3-486-25808-7

Übungen:

Übungsaufgabe 1

Ergänzungen - Material zur Übung:

Beispiel CYK-Algorithmus

Akzeptierung und Entscheidung

Unär-binär-Konvertierung mittels Turingmaschine