Formale Grammatik

aus www.iwiki.de, der freien Wissensdatenbank

Eine formale Grammatik besteht aus einer Menge von Terminalen und Nichtterminalen, einem Startsymbol aus der Menge der Nichtterminale sowie einem Produktionssystem.

Inhaltsverzeichnis

1 Schreibweise
2 Beispiele
3 Eigenschaften
4 Typen von formalen Grammatiken
5 Weblinks

[bearbeiten]

Schreibweise

$G = (N, T, P, S t a r t)$

Nichtterminale (N): Eine endliche, nichtleere Menge von Zeichen. Durch Anwendung einer Regel auf ein Nichtterminal kann es in ein anderes Zeichen oder Zeichenkette umgewandelt werden.

Terminale (T): Eine endliche, nichtleere Menge von Zeichen oder Zeichenfolgen. Terminale können durch Regeln des Produktionssystems nicht mehr umgeformt werden, daher der Name Terminal -> im Endzustand. In Büchern und Skripten wird auch oft das Zeichen $Σ$ verwendet.

Start (S): Das Startzeichen $S$ ist ein Zeichen aus der Menge der Nichtterminale, also $Start \in N$

Produktionssystem (P): Jedes Element im Produktionssystem $P$ ist eine Produktion oder (Ersetzungs-) Regel. Eine Regel besteht aus einem Paar $(p, q)$ , oder $p \rightarrow q$ . $p$ steht dabei für die linke Seite einer Regel und $q$ für die rechte Seite. $p$ und $q$ sind Wörter über dem Alphabet $(N \cup T)$ , d.h. $p$ und $q$ können aus allen Terminalen $t \in T$ und Nichtterminalen $n \in N$ bestehen. . Die Schreibweise $p \rightarrow q$ bedeuted also, dass das Wort $p$ durch Anwendung der Regel in das Wort $q$ umgewandelt wird.

[bearbeiten]

Beispiele

Ein Beispiel für eine Grammatik über das Alphabet ${a, b}$ ist $a n b n, n > = 1$ . Die Sprache besteht aus allen Wörtern die mit $n * a$ anfangen und $n * b$ aufhören, zum Beispiel $(ab, aaabbb, a^23b^23, \dots)$ . Mit der Einschränkung $n \geq 1$ wird das leere Wort $ε$ aus der erzeugten Sprache ausgeschlossen.

Es sei $N = {S}$ , $T = {a, b}$ und $S$ das Startsymbol. Das Produktionssystem $P$ besteht aus den Produktionsregeln:

$S \rightarrow aSb$
$S \rightarrow ab$

Andere Schreibweisen für das Produktionssystem:

$P :{(S, a S b),(S, a b)}$
in BNF

<S>  ::=  a<S>b
     |    ab

Grammatik: $G = {N, T, P, S t a r t}$

Das Wort $a a a b b b$ kann abgeleitet werden indem man die Regeln aus $P$ anwendet. Man fange mit dem Startsymbol S an. Nun wird eine Regel auf das Startsymbol angewandt:

$S \rightarrow aSb$ Wort bisher:

a S b

Mit dem anwenden dieser Regel wird das Nichtterminal $S$ in die Folge $a S b$ umgewandelt. Das gleiche nochmal:

$S \rightarrow aSb$ Wort bisher:

a a S b b

Wieder wurde $S$ durch $a S b$ ersetzt. Jetzt wird die zweite Regel angewandt:

$S \rightarrow ab$

Das Resultat: $a a a b b b$ Da sich keine weiteren Nichtterminale im erzeugten Wort befinden kann auch keine weitere Regel mehr angewendet werden. Es wurde ein gültiges Wort aus der Sprache $L (G)$ erzeugt.

[bearbeiten]

Eigenschaften

[bearbeiten]

Mächtigkeit

Die Mächtigkeit einer Sprache hängt davon ab wie stark man die Regeln im Produktionssystem einschränkt. Je mehr Regeln, desto vielfältigere Möglichkeiten gibt es gültige Wörter zu erzeugen.

[bearbeiten]

Mehrdeutigkeit

Eine Grammatik ist mehrdeutig wenn man ein Wort durch mehr als eine Kombination von Produktionsregeln erzeugen kann.

[bearbeiten]

Eindeutigkeit

Ist eine Grammatik eindeutig, kann jedes Wort der erzeugten Sprache nur auf genau einem Weg erzeugt werden, d.h. es gibt für jedes Wort nur einen Syntaxbaum (Ableitungsbaum).

[bearbeiten]

Typen von formalen Grammatiken

Der Linguist Noam Chomsky führte eine Klassifizierung von formalen Grammatiken durch die nach ihm benannte Chomsky-Hierarchie ein. Die Chomsky-Hierarchie unterteilt formale Grammatiken in 4 unterschiedliche Typen. Je höher die Klasse, desto mehr Einschränkungen gelten für die Produktionsregeln einer entsprechenden Grammatik.

Neben den Typen der Chomsky-Hierarchie gibt es noch weitere Grammatiken: