Automaten und Sprachen: Theoretische Informatik für die Praxis

Inhaltsverzeichnis

1. Frontmatter

2. Kapitel 1. Reguläre Sprachen

   Andreas Müller

   Zusammenfassung

   Deterministische endliche Automaten sind die einfachsten Arten von abstrakten Maschinen. Sie definieren aber bereits eine wichtige und praktisch nützliche Klasse von Sprachen, die sogenannten regulären Sprachen. Eine Vielzahl von Algorithmen stehen zur Konstruktion und Optimierung der endlichen Automaten für reguläre Sprachen zur Verfügung.

3. Kapitel 2. Nicht reguläre Sprachen

   Andreas Müller

   Zusammenfassung

   Nicht jede Sprache ist regulär. Das Pumping-Lemma für reguläre Sprachen ist ein praktisch nützliches Werkzeug, welches erlaubt zu erkennen, wenn man den Bereich der regulären Sprachen verlässt.

4. Kapitel 3. Nichtdeterministische endliche Automaten

   Andreas Müller

   Zusammenfassung

   Nichtdeterminismus ist ein mächtiges Werkzeug, mit dem die Konstruktion und das Studium von endlichen Automaten vereinfacht werden kann.

5. Kapitel 4. Reguläre Operationen und reguläre Ausdrücke

   Andreas Müller

   Zusammenfassung

   Reguläre Operationen sind die natürlicheren Operationen als die Mengenoperationen von Kapitel 3. Aus ihnen lässt sich mit den regulären Ausdrücken auch eine sehr effiziente und intuitive Spezifikationssprache für reguläre Sprachen entwickeln, die vielfältige Anwendungen hat.

6. Kapitel 5. Kontextfreie Grammatiken und Sprachen

   Andreas Müller

   Zusammenfassung

   Grammatiken ermöglichen viele Sprachelemente zu spezifizieren, für die reguläre Sprachen nicht reichen. Der daraus abgeleitete Syntaxbaum eines Sprachausdrucks ermöglicht die Auswertung.

7. Kapitel 6. Parsing

   Andreas Müller

   Zusammenfassung

   Grammatiken sind das naheliegende Werkzeug zur Spezifikation einer formalen Sprache. Damit wird die Syntaxanalyse auf der Basis einer Grammatik die wichtigste Aufgabe des Parsers einer Programmiersprache.

8. Kapitel 7. Stackautomaten

   Andreas Müller

   Zusammenfassung

   Der CYK-Algorithmus zur Syntaxanalyse ist viel zu langsam und daher nicht sinnvoll praktisch einsetzbar. Stackautomaten bilden die Basis für ein erfolgreicheres Konzept, den LR-Parser. Fast alle modernen Programmiersprachen können mit einem solchen Parser analysiert werden.

9. Kapitel 8. Nicht kontextfreie Sprachen

   Andreas Müller

   Zusammenfassung

   Grammatiken und Stackautomaten sind nur anwendbar auf kontextfreie Sprachen. Das Pumping-Lemma für kontextfreie Sprachen ist ein handliches Werkzeug, um Sprachen als nicht kontextfrei zu erkennen.

10. Kapitel 9. Abzählbar und überabzählbar unendlich

    Andreas Müller

    Zusammenfassung

    Sprachen basieren immer auf einem endlichen Alphabet und setzen sich aus endlichen Wörtern zusammen. Trotzdem können Sprachen unendlich viele Wörter haben. Es ist daher wichtig zu verstehen, was unendlich genau heißt. Die Menge aller Wörter ist abzählbar unendlich, die Menge aller Sprachen dagegen überabzählbar.

11. Kapitel 10. Turing-Maschinen

    Andreas Müller

    Zusammenfassung

    Die Turing-Maschine ist die mathematische Abstraktion eines Computers. Es zeigt sich, dass die vielen Varianten von Turing-Maschinen alle im Wesentlichen die gleichen Fähigkeiten haben und damit ein gutes Modell sind, um mathematische Aussagen über reale Computerprogramme zu erhalten.

12. Kapitel 11. Entscheidbarkeit

    Andreas Müller

    Zusammenfassung

    Nicht jede Aufgabe lässt sich mit einem Computer lösen. Das von Alan Turing entdeckte Halteproblem ist wahrscheinlich das berühmteste solche Problem. Es steht aber nicht alleine, eine ganze Familie von Problemen sind nicht entscheidbar.

13. Kapitel 12. Komplexität

    Andreas Müller

    Zusammenfassung

    Zu lange Laufzeit ist der häufigste Grund für unbefriedigende Leistung einer Anwendung in der Praxis. Oft ist nicht die Hardware schuld, sondern das Problem ist grundsätzlich schwierig. Die Komplexitätstheorie untersucht hardwareunabhängige Eigenschaften von Algorithmen, deren Performance nicht skalieren wird und gibt dem Praktiker damit ein Entscheidungswerkzeug in die Hand, wie er problematische Anwendungsteile von vornherein so gestalten, kann dass er diesen Schwierigkeiten aus dem Weg gehen kann.

14. Kapitel 13. NP-Vollständigkeit

    Andreas Müller

    Zusammenfassung

    Unter den NP-Problemen sind jene besonders interessant, auf die sich alle anderen polynomiell reduzieren lassen. Dass es solche Probleme überhaupt gibt, ist die überraschende Aussage des Satzes von Cook-Levin. Eine große Zahl von NP-vollständigen Problemen gibt dem Praktiker die Möglichkeit, durch Vergleich Skalierungsprobleme in Aufgabenstellung in der Praxis rechtzeitig zu erkennen.

15. Kapitel 14. Programmiersprachen und Turing-Vollständigkeit

    Andreas Müller

    Zusammenfassung

    In der Praxis werden Turing-Maschinen mit höheren Programmiersprachen programmiert. Dabei besteht die Gefahr, dass wichtige Fähigkeiten der Turing-Maschine durch die verwendete Sprache eingeschränkt werden. Durch sorgfältig konstruierte primitive Programmiersprachen kann man herausfinden, welche Sprachelemente notwendig sind, um die Fähigkeiten einer Turing-Maschine zu erlangen.

16. Kapitel 15. Quantencomputer

    Andreas Müller

    Zusammenfassung

    Quantencomputer versprechen die Lösung gewisser besonders schwieriger Probleme. So wie klassische Computer eine physikalische Realisierung des mathematischen Konzepts der Turing-Maschine mit Hilfe der klassischen Physik sind, versucht ein Quantencomputer eine nach den Gesetzen dar mathematischen Theorie der Quantenberechnung ablaufende Berechnung mit quantenphysikalischen Messungen zu realisieren. Die Überlagerung von Teilchenzuständen ist dabei das zentrale Werkzeug, welches exponentielle Beschleunigung in gewissen Problemen ermöglichen könnte.

17. Kapitel 16. Grundlagen und Bezeichnungen

    Andreas Müller

    Zusammenfassung

    Die theoretische Informatik braucht die elementare mathematische Logik und die Mengenlehre als Grundlage. Im Anhang werden die im Buch benötigten Grundlagen zusammengestellt und die verwendete Schreibweise festgelegt.

18. Backmatter