Automaten und Sprachen

Theoretische Informatik für die Praxis

Die in diesem Buch dargestellte theoretische Informatik stellt mathematische Abstraktionen bereit, mit denen alltägliche informatische Aufgabenstellungen besser verstanden und analysiert werden können. Sie gibt mathematisch zuverläßige Antworten darauf, ob eine Aufgabenstellung mit einem bestimmten Werkzeug gelöst werden kann. Endliche Automaten definieren die sogenannten regulären Sprachen und bilden die Basis für reguläre Ausdrücke und ihre Implementation. Das Pumping Lemma für reguläre Sprachen gibt ein handliches Werkzeug um zu erkennen, wenn eine Sprache nicht regulär ist und daher die Verwendung von regulären Ausdrücken nicht zielführend sein wird.

Kontextfreie Grammatiken werden zur Spezifikation formaler Sprachen verwendet. Parser-Generatoren verwenden Stackautomaten, um aus einer Grammatik automatisch den Code für einen Parser zu generieren. Wieder wird ein Pumping-Lemma helfen, Sprachen zu erkennen, die nicht kontextfrei sind und daher nicht mit so einem Parser behandelt werden können.

Alan Turings Konzept der Turing-Maschine stellt ein Modell für einen Computer bereit, das einfach genug ist, eindeutige mathematische Aussagen über die Möglichkeiten eines Computers zu gewinnen. Andererseits sind Turing-Maschinen allgemein genug, dass man argumentieren kann, dass alle modernen Computer nicht mehr können als Turing-Maschinen, sondern nur schneller. Es war eine besonders revolutionäre Erkenntnis von Turing, dass es Aufgabenstellungen gibt, die grundsätzlich nicht von einem Computer entschieden werden können. Entscheidbarkeit ist ein für den Anfängerstudenten der theoretischen Informatik besonders schwieriges Thema. Der von Ai Shimizu gezeichnete Entscheider wird dem Leser hoffentlich helfen.

Schon in der Automatentheorie begegnen Studierende dem Konzept des Nichtdeterminismus. Bei endlichen Automaten hat die Verwendung von nichtdeterministischen Automaten messbare und anwendungsrelevante Konsequenzen für die Arbeitsgeschwindigkeit. Stackautomaten sind grundsätzlich nichtdeterministisch, so dass man nicht erwarten kann, dass die grundlegende Aufgabe der Syntaxanalyse sich mit hoher Geschwindigkeit lösen lässt. Nur für eine kleinere Klasse von Sprachen sind effiziente Parse-Algorithmen bekannt. Und den Unterschied der Komplexitätsklassen P und NP kann man nur würdigen, wenn man ein solides Verständnis für Nichtdeterminismus erarbeitet hat. Auch hier kann hoffentlich die Figur des Orakels, der guten Fee, die den Nichtdeterminismus auflösen kann, dem Studierenden helfen.

Mehr zum Inhalt des Buches.

Der Autor

Prof. Dr. Andreas Müller ist seit 2006 Professor für Mathematik an der OST Ostschweizer Fachhochschule in Rapperswil. Nicht nur den Unterricht in den Grundlagenfächern sondern auch Studienarbeiten oder sein mathematisches Seminar gestaltet er nach dem Grundsatz, dass gute Mathematik auch zu guten Ingenieurslösungen in angewandten Problemstellungen führt. Er wurde 2015 als erster Dozent der OST mit dem Credit Suisse Award for Best Teaching ausgezeichnet.

Die nebenstehende Karikatur des Autors hat Ai Shimizu gezeichnet.

Bezug

Das Buch erschien am 22. November 2024 bei Springer-Vieweg.

Website zum Buch

Die Website zum Buch bietet zusätzliche Unterstützung beim Lernen der theoretischen Informatik:

  • Einige Konzepte sind mit Videos illustriert, die im Buch über QR-Codes verlinkt sind.
  • Begriffe, Definitionen und Sätze der linearen Algebra kann man mit Hilfe von Anki-Lernkarten studieren.
  • Das Buch ist elektronisch erweiterbar. Ergänzungsartikel zur Vertiefung der Theorie oder zu weiteren Anwendungen sind unter dem Menupunkt Artikel abrufbar.
  • Die Musterlösungen zu den Übungsaufgaben im Buch können unter Übungen gefunden werden. Dort findet man auch zusätzliche Übungsaufgaben zur Vertiefung, Training oder Prüfungsvorbereitung.