Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenFreitag, 21. Februar 2020 

Formale Grammatik


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Formale Grammatiken sind mathematische Modelle von Grammatiken die so genannte formale Sprachen erzeugen und besonders in der theoretischen Informatik insbesondere bei Berechenbarkeitstheorie und dem Compilerbau Anwendung finden.

Definition

Eine formale Grammatik <math>G</math> ist ein 4- Tupel bestehend aus einer endlichen Menge <math>N</math> Nichtterminalsymbolen (im Folgenden kurz Nichtterminale oft aber auch Variablen genannt) einer endlichen Menge <math>\Sigma</math> von Terminal symbolen (im Folgenden kurz Terminale genannt) (wobei das Alphabet <math>\Sigma</math> und Nichtterminale N disjunkt sind) einer endlichen Menge <math>P</math> von Produktionsregeln (im Folgenden kurz Regeln oft auch Produktionen genannt) und einem Startsymbol <math>S</math> welches zu den Nichtterminalen gehört:

<math>G = \left( N \Sigma P \right)</math> <math>S \in N</math> <math>N \cap \Sigma \empty</math>

Nichtterminale werden gewöhnlich durch Großbuchstaben Terminale Kleinbuchstaben repräsentiert.

Eine Regel besteht aus einer linken einer rechten Seite die jeweils ein Wort aus Terminalen und Nichtterminalen sind. Die rechte kann dabei im Gegensatz zur linken Seite das leere Wort (im Folgenden mit <math>\epsilon</math> symbolisiert) sein das Wort welches keine Symbole enthält:

 <math>P \subseteq \left( N \cup \Sigma \cdot N \cdot \left( N \cup \Sigma \times \left( N \cup \Sigma \cup \{ \} \right)^*</math>  

Eine Regel kann auf ein Wort aus Terminalen und Nichtterminalen angewendet werden wobei beliebiges Vorkommen der linken Seite der Regel Wort durch die rechten Seite der Regel wird. Für solche Produktionen hat sich folgende eingebürgert:

<math>w \rightarrow w'</math>

Eine Folge von Anwendungen solcher Regeln man als Ableitung siehe dort.

Von <math>G</math> erzeugte Sprache

Eine Grammatik <math>G</math> erzeugt eine formale Sprache <math>L \left( G \right)</math> die aus Wörtern besteht die nur aus Terminalen bestehen vom Startsymbol abgeleitet werden können:

<math>L \left( G \right) := \left\{ \in \Sigma^* | S \Rightarrow_G^* w \right\}</math>

<math>\Rightarrow_G</math> symbolisiert hierbei die so genannte Transitionsrelation siehe dort.

Beispiel

Wir betrachten die Grammatik mit den <math>\{a b\}</math> den Nichtterminalen <math>\{S A B\}</math> dem Startsymbol <math>S</math> und den Regeln

 <math>S \rightarrow ABS</math> <math>S \rightarrow \epsilon</math> \rightarrow AB</math> <math>BS \rightarrow b</math> <math>Bb \rightarrow <math>Ab \rightarrow ab</math> <math>Aa \rightarrow aa</math>  

Sie definiert die Sprache aller Wörter Form <math>a^n b^n | n \in N_0</math> <math>n</math> Kopien von <math>a</math> gefolgt von <math>n</math> von <math>b</math>.

Hierbei ist zu beachten das dies die einzige Grammatik ist die diese Sprache Eine weitere Grammatik zur Erzeugung von <math>a^n | n \in N_0</math> ist die mit Regeln

 <math>S \rightarrow ASB | \epsilon</math> <math>A a</math> <math>B \rightarrow b</math>  

Man sieht also das es zur einer Sprache mehrere (genaugenommen: beliebig viele) Grammatiken

Man klassifiziert verschiedene Typen von Grammatiken der so genannten Chomsky-Hierarchie .



Bücher zum Thema Formale Grammatik

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Formale_Grammatik.html">Formale Grammatik </a>