Formale Sprachen - Einleitung

Die theoretische Informatik befasst sich mit der Berechenbarkeit von Problemen und wie diese effizient gelöst werden können. Diese Probleme werden in formale Sprachen „formuliert“, welche uns erst die Untersuchung und Berechnungen ermöglichen.

Ein Algorithmus ist berechenbar, wenn er für alle Eingaben ein Ergebnis liefert. Die Berechnung kann egal mit welchem Rechner (maschinell oder menschlich) durchgeführt werden. Leider gibt es in dieser Aussage ein Problem: Begriffe wie maschineller oder menschlicher Rechner sind zu unpräzise, um eine exakte mathematische Aussage über die Berechenbarkeit von Algorithmen zu treffen. Deshalb benötigt man ein mathematisches Modell, welches den Begriff der Berechenbarkeit exakt beschreibt. Ein solches Berechnungsmodell wurde bereits 1936 von Alan Turing erstellt - die Turingmaschine.

Es gibt allerdings Probleme bzw. Algorithmen, die nie gelöst werden können. So zum Beispiel das Halteproblem, welches "nicht-berechenbar" ist.

In der Komplexitätstheorie stellt man sich die Frage, wie schnell ein Algorithmus Probleme löst und wie viel Platz bzw. Ressourcen er benötigt.

"Ein Automat oder eine abstrakte Maschine ist in der Informatik, speziell in der Automatentheorie, das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der Fähigkeiten erlaubt es, das Verhalten eines Automaten leichter zu verstehen und zu vergleichen."
Quelle: https://de.wikipedia.org/w/index.php?title=Automat_(Informatik)&oldid=163057861

Automaten sind somit Berechnungsmodelle für formale Sprachen. Das bedeutet, dass ein Automat entscheidet, ob ein Wort zu einer Sprache gehört oder nicht. Wenn es einen Weg gibt der in den Endzustand des Automaten führt, wird das Wort akzeptiert. Gibt es keinen Weg zum Endzustand, gehört das Wort nicht zur gegebenen Sprache.

Ein deterministischer endlicher Automat besteht aus Zuständen, Übergangsfunktionen, einem Eingabealphabet, einem Anfangszustand und einem oder mehreren Endzuständen. Der Automat befindet sich nach einer Folge von Eingaben in einem entsprechenden Zustand. In Abhängigkeit des Zustandes und eventuell weiterer Eingaben, wechselt der Automat in einen Folgezustand. Bei deterministischen endlichen Automaten besteht immer nur eine Möglichkeit der Fortsetzung – also 1 Folgezustand!

Nichtdeterministische endliche Automaten können hingegen zu einem Zustand und zu einer Eingabe mehrere Folgezustände haben.

Formale Sprachen werden aus Alphabeten A, Worten w und Grammatiken G beschrieben. Ein Alphabet ist in diesem Fall eine endliche Aneinanderreihung von Symbolen bzw. Zeichen. Ein Wort ist folglich eine endliche Folge an Symbolen des Alphabets. Unter Konkatenation versteht man das Aneinanderhängen von Wörtern. Ein Palindrom ist ein eine Zeichenfolge (also ein Wort), welches vorwärts und rückwärts gelesen das gleiche ergeben.

Da es sich bei (formalen) Sprachen um Mengen handelt, können alle mathematischen Mengenoperationen darauf angewendet werden. Dazu zählen der Schnitt (A ∩ B), die Vereinigung (A ∪ B), die Differenz (A \ B) und das Komplement (C(A)). Das Komplement einer Menge A, ist definiert als die Menge aller Elemente die nicht in A enthalten sind. Auch die Beziehung zwischen Mengen und Elementen kann durch mathematische Mengenrelationen wie, der Teilmenge (A ⊆ B) oder der echten Teilmenge (A ⊂ B) abgebildet werden.

Die Grammatik gibt an unter welchen „Regeln“ ein Wort aus dem gegebenen Alphabet gebildet werden kann. Es ist also eine Art Vorschrift für die formale Sprache. Grammatiken werden mit dem Buchstaben G abgekürzt und bestehen aus V, Σ, P und S.

Die Chomsky Hierarchie klassifiziert formale Grammatiken. Jede Grammatik ist mindestens eine Typ-0-Grammatik. Weist die Grammatik weitere Einschränkungen auf, wird sie in höhere Stufen eingeteilt. Die Menge der aus jedem Grammatik-Typ erzeugten Wörter, können zu einem Sprachtyp zusammengefasst werden. Deshalb hört man auch öfter die Begriffe Typ-0/1/2/3-Sprache.

X → aY ; X → a ; X → ε

mit X, Y ∈ V und a ∈ Σ

Die reguläre Grammatik ist ein Spezialfall der Typ-2-Grammatik. Auf der linken Seite steht immer eine Variable. Eine Variable kann entweder zu einem kleinen Buchstaben gefolgt von einer Variable abgeleitet werden, nur zu einem kleinen Buchstaben oder zum leeren Wort. Dabei sind die Buchstaben Terminale aus dem gegebenen Alphabet.

Beispiel: deterministischer und nichtdeterministischer endlicher Automat (DEA / NEA), reguläre Ausdrücke

X → w

mit X ∈ V, w ∈ A*

Bei diesem Grammatiktyp steht auf der linken Seite lediglich eine Variable und auf der rechten ein beliebiges Wort aus dem Alphabet A*.

Beispiel: Kellerautomaten, kontextfreie Grammatiken

w1 → w2

mit |w1|≤|w2| und S → ε

Die kontextsensitive Grammatik ähnelt der allgemeinen Grammatik. Die Typ-1-Grammatik weist im Gegensatz zur Typ-0-Grammatik einen Spezialfall auf, um das leere Wort ε zu erzeugen.

w1 → w2

mit w1 ∈ A+, w2 ∈ A*

Die Allgemeine Grammatik unterliegt keinerlei Einschränkung. Deshalb ist jede Grammatik, mindestens eine Typ-0 Grammatik. Auf der linken Seite steht ein beliebiges Wort aus A⁺ (ohne leeres Wort), auf der rechten Seite ein beliebiges Wort aus dem Alphabet A*

Beispiel: Turingmaschinen