[Logo of DHBW Stuttgart]

Formale Sprachen und Automatentheorie

Vorlesung an der DHBW Stuttgart, 2016.

Stephan Schulz und Jan Hladik

Inhalte

Formale Sprachen bilden die Grundlage für die Beschreibung und Umsetzung von Eingabesprachen für Computer - von speziellen Konfigurationssprachen über HTML und XML bis hin zu echten Programmiersprachen wie C, JAVA, und LISP. Aber auch die Verarbeitung und das Verständnis von natürlichsprachlichen Texten stützt sich auf formale Sprachen.

In dieser Vorlesung erschließen wir, wie solche Sprachen beschrieben werden können, und wie man Worte (Texte, Programme, Dokummente) wieder parsen kann, also wie man aus einer Folge von Buchstaben die syntaktische Struktur des entsprechenden Textes ableiten kann.

Die Automatentheorie bietet dafür Berechnungsmodelle, mit denen wir verschiedene Klassen von Sprachen erkennen und verarbeiten können. Endliche Automaten können eine Sprache z.B. in Schlüsselworte, Bezeichner, Hilfssymbole und elementare Werte zerlegen. Mächtigere Automatenmodelle können zunehmend kompliziertere Konstrukte erkennen und verarbeiten. Die Turing-Maschine ist ein Modell eines universellen Computers. Turing-Maschinen können mit einfachsten Mitteln die selben Berechnungen durchführen wie idealisierte Versionen unserer heutigen Computer.

Unterlagen

DHBW Stuttgart, Prof. Dr. Stephan Schulz