Zum Hauptinhalt springen

2. Formale Sprachen

Wozu brauchen wir überhaupt formale Sprachen?​

Einige Anwendungsbeispiele bzw. formale Sprachen:

  • Compilerbau -> Syntaxanalyse von Programmiersprachen (z. B. C, Java)
  • Datentausch -> Strukturierte Formate wie HTML, XML, JSON
  • Formatierung, Validierung und Spezifikation -> Prüfen von Formulareingaben oder Protokollabläufen
  • Datenbanken -> Mustersuche in Abfragen (z. B. reguläre Ausdrücke (REGEX) in SQL)

Compiler​

Ein Compiler übersetzt einen Quellprogramm in Maschinen- oder Bytecode in mehreren Phasen:

  1. Lexikalische Analyse: Ein Lexer / Tokenizer erzeugt eine Folge von Tokens (Bedeutungseinheiten) und übergibt diese an den Parser. Kommentare und Leerzeichen werden ignoriert. Schlüsselwörter (if, while, class...), Operatoren, Bezeichner (lengthCm), Literale (2.54, "Hello Worlds") werden erkannt.

Beispiel: Quellcode ---> Tokens lengthCm = lengthInch * 2.54; ---> NAME EQUALS NAME START NUMBER SEMICOLON

  1. Syntaktische Analyse: Der Parser erkennt Makrostrukturen (Funktionen, Schleifen usw.) und wandelt sie in einen Strukturbaum umgewandelt.

  2. Semantische Analyse: Aus dem Strukturbaum findet die tatsächliche Übersetzung statt (=Codeerzeugung bzw. Optimierung).

info

Was ist ein Bezeichner?

In der Informatik werden Bezeichner durch formale Grammatiken spezifiziert. Grammatiken sind präzise, abstrakt, kompakt und für Menschen und Maschinen verständlich. Sie sind damit die bevorzugte Art, Sprachen in der Informatik (wie Programmiersprachen oder Datenformate) zu beschreiben und zu analysieren.

Beispiel Formale Grammatik:

Bezeichner ::= Buchstabe | Buchstabe InBezeichner
InBezeichner ::= BuchOderZiff | BuchOderZiff InBezeichner
BuchOderZiff ::= Buchstabe | Ziffer
Buchstabe ::= "a" | "b" | ... | "Z"
Ziffer ::= "0" | "1" | ... | "9"

Grundbegriffe​

Alphabet​

Ein Alphabet ist eine endliche, nicht leere Menge. Elemente des Alphabets heißen Symbole.

Wort​

Ein endliches Wort über einen Alphabet Σ (Sigma) ist eine endliche Folge von Symbolen aus Σ. Wenn ω (klein Omega) ein endliches Wort ist, dann ist |ω| seine Länge (die Anzahl seiner Symbole).

Beispiel Alphabet:

Σ = {a, b} ist ein Alphabet.
Wörter über diesem Alphabet sind z.B. "abba" oder "bbb"
Die Längen dieser Wörter sind |abba|= 4 und |bbb|= 3.

Tupeln​

Eine endliche Sequenz von Elementen nennt man Tupel. Tupel werden mit runden Klammern angegeben, also zum Beispiel (1, 3, 5, 3). Tupel aus k Elementen nennt man auch k-Tupel. Mit Paaren bezeichnet man 2-Tupel, und mit Tripeln bezeichnet man 3-Tupel. Im Gegensatz zu Mengen sind die Elemente eines Tupels geordnet, das heißt, (1, 3) ist nicht gleich (3, 1). Außerdem können Elemente doppelt auftreten.

Konkatenation, Leeres Wort​

Die Konkatenation von zwei Wörtern ω und ν ist das Wort ων

Das leere Wort ϵ (epsilon) ist das Wort der Länge 0, also |ϵ| = 0

Formale Sprache​

Eine formale Sprache ist einfach eine Menge von Wörtern über einem gegebenen Alphabet Σ. Notation: Formale Sprachen werden üblicherweise mit dem Buchstaben L bezeichnet. Beispiel für eine endliche Sprache: Ziffern = { "0", "1", ..., "9" } besteht aus einzelnen Symbolen des Alphabets.

Die kleinste Sprache über dem Alphabet Σ ist die leere Sprache 0.

Die Sprache {ϵ}, welche nur das leere Wort enthält, ist nicht leer!

Eine leere Menge ist != eine Menge, die eine leere Menge enthält.

Die größte Sprache über einem Alphabet Σ ist die Sprache aller Wörter über Σ und wird mit Σ* ("Sigma Stern") bezeichnet.

Wichtige Operationen mit formalen Sprachen:​

Vereinigung (Union)​

Zwei Sprachen zusammenlegen.

Notation: L₁ ∪ L₂ Bedeutung: Alle Wörter, die in L₁ oder L₂ oder beiden sind.

Beispiel:

    L₁ = {a, ab}, L₂ = {b, bb}

    L₁ ∪ L₂ = {a, ab, b, bb}

Konkatenation (Verkettung)​

Wörter aus L₁ hinter Wörter aus L₂ hängen.

Notation: L₁ · L₂ oder einfach L₁L₂ Bedeutung: Alle Wörter der Form xy mit x ∈ L₁, y ∈ L₂

Beispiel:

    L₁ = {a, b}, L₂ = {c}

    L₁ · L₂ = {ac, bc}

Schnitt (Durchschnitt)​

Nur die Wörter, die in beiden Sprachen gleichzeitig sind.

Notation: L₁ ∩ L₂

Beispiel:

    L₁ = {a, ab, abc}, L₂ = {ab, abc}

    L₁ ∩ L₂ = {ab, abc}

(bei regulären Sprachen nur über Automaten direkt lösbar)

Komplement​

Alles, was nicht in der Sprache ist (bezogen auf ein festes Alphabet).

Notation: ¬L oder Σ* \ L

Bedeutung: Alle Wörter, die nicht in L sind, aber im Universum (z. B. Σ*).

Die Anzahl der Sprachen​

Ist es möglich, alle Sprache zu beschreiben? Georg Cantor ein deutscher Mathematiker.

Wie viele Wörter gibt es?​

Es gibt unendlich viele Wörter über einem Alphabet mit mindestens einem Symbol.Es gibt abzählbar viele Wörter über jedem Alphabet Σ. Jede Sprache ist also entweder endlich oder abzählbar unendlich.

Die Wörter sind abzählbar, denn man kann alle Wörter systematisch aufzählen:

  • Zuerst alle Wörter der Länge 0 (das leere Wort), dann alle Wörter der Länge 1,dann Länge 2, ... Für jede Länge gibt es nur endlich viele Wörter (da das Alphabet endlich ist)

  • Die Vereinigung all dieser endlichen Mengen über alle Längen ist abzählbar

Wie viele Sprachen gibt es?​

Georg Cantor. Es gibt überabzählbar viele Sprachen über jedem beliebigen Alphabet Σ. Man stelle sich eine unendliche Tabelle vor:

  • Zeilen: Alle möglichen Sprachen L1,L2,L3,… (angenommen, wir hätten sie abzählbar aufgelistet)

  • Spalten: Alle Wörter ω1,ω2,ω3,… (die Wörter sind abzählbar)

  • Das Element in Zeile i, Spalte j zeigt, ob das Wort ωj​ in der Sprache Li​ enthalten ist (z.B. mit 1 = „drin“, 0 = „nicht drin“).

  • Jetzt konstruiert man eine neue Sprache L∗, die in Spalte j das Wort ωj​ genau dann enthält, wenn das Wort ωj​ nicht in der Sprache Lj (also der j-ten Sprache auf der Liste) enthalten ist.

  • Durch diese Konstruktion unterscheidet sich L∗ von jeder aufgelisteten Sprache Lj​ mindestens im Wort ωj​ (weil genau dort das Gegenteil steht).

  • Folglich ist L∗ nicht in der ursprünglichen Liste enthalten.

Damit zeigt man, dass keine abzählbare Liste alle Sprachen enthalten kann → die Menge aller Sprachen ist überabzählbar.