Theoretische Informatik Grundlagen Übungen mit Lösungen

This page contains exercises and solutions about the basics of theoretical computer science. Even though the material is in German, you should be able to understand most of it without deeper knowledge in the German language as most of the material is formal notation.

Diese Seite beinhaltet die Übungsblätter und Lösungen sowie weiterführende Zusammenfassungen, die ich im Wintersemester 2001/ 2002 als Tutor für meine Studenten erstellt habe.

Zugrunde liegt die Vorlesung Theoretische Informatik im Wintersemester 2001/ 2002, die von Prof. Dr. Klaus-Jörn Lange an der Universität Tübingen gehalten wurde.

Die Üungsblätter wurden von Dr. Klaus Reinhardt zusammengestellt.

Die Vorlesung basiert auf dem Buch:

Uwe Schöning, Theoretische Informatik -- kurzgefaßt, dritte Auflage
Spektrum Akademie Verlag, Deutschland, 1997
ISBN-10: 3-8274-0250-6,
ISBN-13: 9783827402509

Die Materialien eignen sich sehr gut zum Selbstlernen und zur Vorbereitung auf eine Prüfung in den behandelten Bereichen.

Viel Spaß mit den Aufgaben!

Verweise auf Seitenzahlen des Buches beziehen sich auf die DRITTE Auflage des Schöning. Es besteht kein Anspruch auf Korrektheit der Lösungen wenngleich sie gewissenhaft verfasst und geprüft wurden.

• 0. Diskrete Mathematik

  ---

  • Übungsblatt: | Lösung:
  • Konstruktion einer Grammatik für die Sprache aller Wörter die mit "ab" beginnen/ die "ab" enthalten:
• 1. Grammatiken

  ---

  • Übungsblatt: | Lösung:
  • Tipps
  • Lösung zu Aufgabe 5:
  • Infos zu den Chomsky-Typen:
  • Hinweise zur Notation {a,b}*; (ab)* etc.
• 2 Grammatiken 2

  ---

  • Übungsblatt: | Lösung:
• 3. Reguläre Sprachen

  ---

  • Übungsblatt: | Lösung:
  • DEA der Wörter mit Vielfachen von fünf a's erkennt und Beweis seiner Korrektheit durch Wortinduktion:
• 4. Reguläre Sprachen/ Ausdrücke

  ---

  • Übungsblatt: | Lösung:
  • Alles Wissenswerte zum Verfahren ?FA -> regulärer Ausdruck:
  • DFA -> rA am Beispiel von Blatt 4 Aufgabe 5 mit zwei unterschiedlichen Indizierungen:
• 5. Reguläre Sprachen

  ---

  • Übungsblatt: | Lösung:
  • Myhill/ Nerode
• 6. Reguläre Sprachen und kontextfreie Sprachen

  ---

  • Übungsblatt: | Lösung:
• 7. Kontextfreie Sprachen

  ---

  • Übungsblatt: | Lösung:
  • Wie komme ich zur Greibach-Normal-Form?
• 8. Kellerautomaten

  ---

  • Übungsblatt: | Lösung:
  • Grammatik Typ 2 -> NPDA am Beispiel von Blatt 8 Aufgabe 1.2
    NPDA -> Grammatik Typ 2 am Beispiel von Blatt 8 Aufgabe 3d)
• Zusammenfassung

  ---

  • Was haben wir bisher gelernt?
• 9. Turingmaschinen

  ---

  • Übungsblatt: | Lösung:
  • Die 5a) wurde am 13.1.2002 (nach der Übungsgruppe) nochmal korrigiert [ist bei der Lösung zur 9 dabei]:
• 10. Turing- und Loop-Berechenbarkeit

  ---

  • Übungsblatt: | Lösung:
• 11. While- und Goto-Programme, primitive Rekursion

  ---

  • Übungsblatt: | Lösung:
• 12. Rekursive Funktionen

  ---

  • Übungsblatt: | Lösung:
• 13. Entscheidbarkeit, Reduzierbarkeit

  ---

  • Übungsblatt: | Lösung:
• 14. Postsches Korrespondenzproblem (PCP)

  ---

  • Übungsblatt: | Lösung:
• Zusammenfassung

  ---

  • Kapitel 2
• 15. Komplexität

  ---

  • Übungsblatt: | Lösung:
  • Aufgabe2
• Turing Maschine

  ---

  • Hier findet sich noch eine Java Applet zur Turing Maschine (lokale Kopie von der Website von Klaus-Jörn Lange, Universität Tübingen)