Formale Sprachen

Eine Sprache definiert eine Menge von Wörtern, welche zur Sprache gehören.

Beispiel:

L(A) = {abba} 
    Akzeptiert nur abba
L(A) = {a^nb | n aus N}
    Akzeptiert beliebieg viele 'a' mit 'b' am Ende, wie aaaab aab oder auch nur 'b', da n auch =0 sein kann.

Grammatiken

Jede Sprache ist nach bestimmten Regeln aufgebaut. Sprachen bestehen aus der Syntax(Form der Wörter) und Semantik(Bedeutung). Die Syntax wird durch die Grammatik definiert. Sprich, man kann eine formale Sprache durch eine Grammatik beschreiben

Eine Grammatik besteht aus Terminalsymbolen und Nichtterminalsymbolen. Jedes Wort der Sprache besteht aus einer Folge von Terminalsymbolen. Nichtterminalsymbole werden von der Grammatik weiter zu anderen Nichtterminalsymbolen oder Terminalsymbolen abgeleitet.

graph TD A(Satz) --> B(Prädikat) A --> C(Substantiv) A --> D(Objekt) D --> E(Artikel) D --> F(Substantiv) E --> G[Der] F --> H[Hund] B --> I[erschreckt] C --> J(Objekt) J --> K(Artikel) J --> L(Substantiv) K --> M[die] L --> N[Katze] X(Nichtterminalsymbol) --> Y[Terminalsymbol]

Definition

Eine Grammatik G ist gegeben durch die folgenden vier Bestandteile G = (N, T, R, S)

  • N ist eine endliche Menge von Nichtterminalsymbolen
  • T ist eine endliche Menge von Terminalsymbolen
  • R ist eine endliche Menge von Ableitungsregeln
  • S ist eine Nichtterminalsymbol, das das Startsymbol ist

Eine Grammatik heißt regulär, wenn alle Ableitungsregeln von der Form

A -> xB oder A -> x sind. Eine Sprache heißt regulär, wenn sie von einer regulären Grammatik erzeugt wird.

Jede reguläre Sprache kann von einem passenden endlichen Automaten akzeptiert werden.

  • Eine Grammatik erzeugt eine Sprache
  • Ein Automat prüft eine Sprache

Grammatik zu endlichem Automaten

Wenn man einen endlichen Automaten aus einer regulären Grammatik konstruieren will, muss man mehrere Regeln beachten:

  1. Die Menge der Terminalsymbole der Grammatik ist das Alphabet des Automaten
  2. Die Menge der Nichtterminalsymbole der Grammatik ist zumindest ein Teil der Zustände des Automaten
  3. Das Startsymbol der Grammatik ist der Startzustand des Automaten
  4. Zu jeder Ableitungsregel A -> xB wird ein Übergang (A) --x--> (B) gebildet.

Die Endzustände des Automaten kommen von den Übergängen der Grammatik in denen auf der rechten Seite nur ein Terminalsymbol steht, also A -> x.

Beispiel:

  • T = {a, b}
  • N = {S, U, V, W}
  • R = {S -> aS|bU, U -> aV, V -> aU|bW, W->b}
  • Startsymbol ist S

Wir wissen schon direkt, dass W der einzige Endzustand ist und S der Startzustand ist. Graph von Automat

Kontextfreie Grammatiken

Eine Grammatik ist eine weiter gefasste reguläre Grammatik. Sie ist nicht mehr von dem entsprechenden Kontext(Zustand des Automaten) Abhängig. Sie können durch Kellerautomaten dargestellt werden.

  • Sie ist nicht mehr durch einen EDA darstellbar
  • Sie kann auch Übergänge, wie A -> xBC oder A -> xAx enthalten