Formale Grammatik


Formale Grammatik

Formale Grammatiken sind mathematische Modelle von Grammatiken, die mit Hilfe des Semi-Thue-Systems angegeben werden und durch die formale Sprachen beschrieben und erzeugt werden können. Sie werden in der theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie, und im Compilerbau angewandt, um zum einen eine formale Sprache eindeutig zu beschreiben (d. h. um eindeutig festzulegen, ob ein Wort Element einer Sprache ist, oder nicht) und um zum anderen Eigenschaften dieser formalen Sprachen zu untersuchen bzw. zu beweisen. Formale Grammatiken werden in der Chomsky-Hierarchie klassifiziert.

Inhaltsverzeichnis

Beschreibung

Mit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol S Produktionsregeln aus einer Regelmenge P anwenden, die aus dem Startsymbol neue Zeichenfolgen erzeugen, welche wiederum weiter ersetzt werden können. Diesen Vorgang nennt man auch Ableitung.

Das Vokabular V einer Grammatik, bestehend aus Terminalsymbolen Σ und Nichtterminalsymbolen N, gibt dabei vor, welche Symbole dafür verwendet werden können. Die Menge der Terminalsymbole definiert, aus welchen Zeichen Wörter bestehen, die nicht weiter abgeleitet werden können. Diese Wörter ergeben zusammengenommen die von der Grammatik beschriebene formale Sprache. Das Startsymbol muss dagegen ein Nichtterminalsymbol sein. Zusätzliche Nichtterminalsymbole erlauben differenziertere Regeln.

Produktionsregeln sind definitionsgemäß Tupel (α,β), die auch \alpha \rightarrow \beta geschrieben werden. Man wendet sie auf eine Zeichenfolge w an, indem ein Vorkommen der Zeichenfolge α in w durch β ersetzt wird. Auf der linken Seite der Regel muss immer mindestens ein Nichtterminalsymbol stehen. Eine Menge von Regeln mit gleicher linker Seite, also \alpha \rightarrow \beta_1,\; \ldots, \alpha \rightarrow \beta_n, wird abkürzend auch als \alpha \rightarrow \beta_1 \;|\; \ldots \;|\; \beta_n geschrieben.

Zum Beispiel kann man mit der Regelmenge X\rightarrow +\;|\;- die Zeichenfolge 1X2 entweder zu 1 + 2 oder zu 1 − 2 ableiten.

Ebenso wie auf eine gegebene Zeichenfolge mehrere Regeln gleichzeitig anwendbar sein können, muss es nicht immer nur eine Stelle in der Zeichenfolge geben, auf die eine Regel passt. Formale Grammatiken schreiben keine Reihenfolge vor. Alle nur aus Terminalsymbolen bestehenden Wörter, die sich aus dem Startsymbol ableiten lassen, zählen zur von der Grammatik beschriebenen Sprache.

Definition

Eine formale Grammatik ist ein 4-Tupel G = (V,Σ,P,S) bestehend aus:[1]

  • V, einer endlichen Menge, welche als Vokabular bezeichnet wird,
  • \Sigma \subset V, einer Teilmenge von V, die Alphabet genannt wird und deren Elemente Terminalsymbole heißen,
  • P \subset \left( V^* \setminus \Sigma^* \right) \times V^*, einer endlichen Menge von Produktionsregeln, sowie
  • S\in V\setminus \Sigma, dem Startsymbol.

Hierbei bezeichnet X * die Kleenesche Hülle von X.

Die Menge N = V\setminus \Sigma ist die Menge von Nichtterminalsymbolen oder auch Metasymbolen.

G als das Tupel (N,Σ,P,S) anzugeben, ist ebenfalls üblich.

Die Erzeugung der von einer Grammatik beschriebenen Sprache

Eine Regel R\rightarrow Q \in P einer gegebenen Grammatik G besagt, dass in einem Wort w \in V^\ast mit R als Infix, dieses durch das Wort Q ersetzt werden kann, so dass ein neues Wort w^\prime mit Q als Infix entsteht. Man spricht hierbei auch davon, dass w in w^\prime mit der Grammatik G bzw. durch die Regel R \rightarrow Q übergeht, oder auch, dass w^\prime aus w abgeleitet wurde. Dies kann durch w \rightsquigarrow_{R \rightarrow Q} w^\prime notiert werden (häufig auch \Rightarrow anstatt \rightsquigarrow). Soll nur ausgedrückt werden, dass in der Grammatik G das Wort w^\prime aus w entstehen kann, ohne eine Regel zu benennen, schreibt man statt dessen w \rightsquigarrow_G w^\prime (ist die Grammatik aus dem Kontext offensichtlich, auch einfach w \rightsquigarrow w^\prime). Demnach ist ein solcher Übergang von w in w^\prime eine Transitionsrelation, die eine natürliche Erweiterung von P auf alle möglichen V * -Kontexte darstellt, nämlich:

\rightsquigarrow\;:=\;\{(u \circ R \circ v, u \circ Q \circ v) | (R,Q)\in P, u,v\in V^*\}.

Gibt es nun eine Folge von Wörtern w_0, w_1, \ldots, w_n \in V^\ast, bei der gilt, dass für jede natürliche Zahl i mit 0 \le i < n das Wort wi in wi + 1 übergeht (w_i \rightsquigarrow_G w_{i+1}), so ist wn in n Schritten aus w0 ableitbar, was durch w_0 \rightsquigarrow_G^n w_n dargestellt wird. Eine solche Wortfolge w_0, w_1, \ldots, w_n wird Ableitung oder Rechnung von w0 in wn der Länge n genannt. Weiterhin heißt w in w^\prime ableitbar, wenn es mindestens ein n \in \mathbb{N}_0 gibt, so dass w^\prime in n Schritten aus w ableitbar ist. Wenn w in w^\prime ableitbar ist, so wird dies durch die Schreibweise w \rightsquigarrow_G^\ast w^\prime dargestellt. Dabei wird zusätzlich definiert, dass für jedes Wort w \in V^\ast gilt, dass w \rightsquigarrow_G^\ast w ist, so dass die Relation \rightsquigarrow_G^\ast die reflexiv-transitive Hülle der Relation \rightsquigarrow_G ist.

Nun ist die von der Grammatik G erzeugte formale Sprache L(G) diejenige Sprache, die aus allen Wörtern besteht, die zum einen nur aus Terminalsymbolen bestehen und die zum anderen vom Startsymbol mit einer endlichen Anzahl von Schritten abgeleitet werden können:

L \left( G \right) := \left\{ w \in \Sigma^* | S \rightsquigarrow_G^* w \right\}

Dabei ist es egal, in welcher Reihenfolge die Produktionsregeln auf die abgeleiteten Wörter angewandt werden, oder ob es mehrere Möglichkeiten gibt, um ein Wort w aus S abzuleiten. Zwei Grammatiken G1 und G2 sind genau dann äquivalent, wenn die durch G1 und G2 erzeugten Sprachen gleich sind:

G_1 \mathrm{\ ist\ \ddot{a}quivalent\ zu\ } G_2: \Longleftrightarrow L(G_1) = L(G_2)

Beispiele

G1 sei eine Grammatik mit den Terminalsymbolen {a,b}, den Nichtterminalsymbolen {S,A,B}, dem Startsymbol S und mit den Regeln


\begin{matrix}
 S&\to&ABS&\,(1)\\
 S&\to&\varepsilon&\,(2)\\
 BA&\to&AB&\,(3)\\
 BS&\to&b&\,(4)\\
 Bb&\to&bb&\,(5)\\
 Ab&\to&ab&\,(6)\\
 Aa&\to&aa&\,(7)
\end{matrix}

Dabei ist ε das leere Wort, welches ein Wort der Länge 0 ist. Diese Grammatik G1 definiert die Sprache aller Wörter der Form anbn mit n \in \mathbb N_0. So sind auf Grund der folgenden Ableitungen die Wörter ε, ab und aabb Elemente der durch G1 beschriebenen Sprache:

  • S\rightsquigarrow\varepsilon, mittels Regel (2),
  • S\rightsquigarrow ABS\rightsquigarrow Ab\rightsquigarrow ab, mittels der Regeln (1), (4) und (6),
  • S\rightsquigarrow ABS\rightsquigarrow ABABS\rightsquigarrow ABAb\rightsquigarrow AABb\rightsquigarrow AAbb\rightsquigarrow Aabb\rightsquigarrow aabb, mittels der Regeln (1),(1),(4),(3), (5), (6) und (7).

Es gibt aber noch andere Möglichkeiten, um das Wort aabb aus S abzuleiten.

Eine weitere Grammatik, die dieselbe Sprache beschreibt, ist die kontextfreie Grammatik G2 mit den Regeln: \begin{matrix}S&\to&aSb\ |\ \varepsilon\end{matrix}

Jede rekursiv aufzählbare Sprache wird von mehreren (und zwar abzählbar unendlich vielen) Grammatiken erzeugt. Allerdings gibt es auch Sprachen, die sich von keiner Grammatik erzeugen lassen.

Klassen von Grammatiken

Grammatiken werden Klassen zugeordnet, die sich durch Gemeinsamkeiten auszeichnen. Die bekannteste Klassifikation beschrieben Noam Chomsky und Marcel Schützenberger mit der Chomsky-Hierarchie.

Chomsky-Hierarchie

Die Chomsky-Hierarchie teilt die Grammatiken nach der Art der Produktionsregeln in Klassen vom Typ 0 bis Typ 3 ein. Typ-0-Grammatiken sind die uneingeschränkten formalen Grammatiken, es folgen kontextsensitive Grammatiken, kontextfreie Grammatiken und reguläre Grammatiken. Die zugehörigen Sprachklassen sind abnehmend umfangreich.

Kontextsensitive Grammatiken dürfen nur aus Regeln bestehen, in denen genau ein Nichtterminalsymbol durch eine Zeichenfolge ersetzt wird. Dieses Symbol darf auf der linken Seite der Regel auch von weiteren Symbolen umgeben sein, die einen Kontext angeben, innerhalb dessen die Ersetzung stattfinden muss.

In kontextfreien Grammatiken darf dagegen auf den linken Seiten der Regeln jeweils nur genau ein Nichtterminalsymbol stehen. Das Symbol kann dann nicht abhängig vom Kontext ersetzt werden.

Bei regulären Grammatiken enthalten die linken Seiten der Regeln ebenfalls nur genau ein Nichtterminalsymbol, zudem bestehen die rechten Seiten der Regeln aus höchstens einem Terminalsymbol, dem höchstens ein Nichtterminalsymbol folgen darf.

Weitere Sprachklassen

Von der Chomsky-Hierarchie abgesehen haben sich weitere Klassen an Grammatiken etabliert. Monotone Grammatiken beschreiben die gleiche Sprachklasse wie die kontextsensitiven Grammatiken. Etwas strenger sind die wachsend kontextsensitiven Grammatiken, die eine Teilklasse der kontextsensitiven Sprachklasse beschreiben. Deterministisch kontextfreie Grammatiken beschreiben die deterministisch kontextfreien Sprachen. Sie werden auch durch die LR(k)-Grammatiken beschrieben, welche für den Compilerbau von Bedeutung sind. Andere im Compilerbau bekannte Grammatiken sind LL(k)-Grammatiken und LF(k)-Grammatiken.

Siehe auch

Literatur

  • Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung. 2. erweiterte Auflage. Springer-Verlag, Berlin u. a. 2002, ISBN 3-540-42624-8, S. 53–61.

Weblinks

Einzelnachweise

  1. Peter Bachmann: Grundlagen der Theoretischen Informatik. Cottbus 2001, S. 47 (Vorlesungsskript, [1], abgerufen am 12. Februar 2011).

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • formale Grammatik — formale Grammạtik,   Grammatik …   Universal-Lexikon

  • formale Sprache — formale Sprache,   eine mithilfe einer formalen Grammatik ableitbare Menge von Zeichenketten. Die formale Grammatik stellt hier die Regeln zur Bildung der Zeichenketten aus einem Zeichenvorrat oder Alphabet zur Verfügung. Bezeichnet man die… …   Universal-Lexikon

  • Grammatik (Begriffsklärung) — Grammatik (griechisch γραμματική, von γράμμα „der Buchstabe“) bezeichnet: Grammatik, einen Teil der Sprachwissenschaft formale Grammatik, ein mathematisches Modell in der theoretischen Informatik Grammatik (artes liberales), ein Gebiet der… …   Deutsch Wikipedia

  • Formale Systeme — Die Artikel Formale Sprache, Formales System, Formales System (Logik) und Kalkül überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Grammatik — Syntax; Satzbau; Satzstruktur * * * Gram|ma|tik [gra matɪk], die; , en: a) <ohne Plural> Lehre vom Bau einer Sprache, ihren Formen und deren Funktion im Satz: die Regeln der lateinischen Grammatik. b) Buch, das den Bau einer Sprache… …   Universal-Lexikon

  • Formale Sprache — Eine formale Sprache ist eine bestimmte Menge von Zeichenketten, die aus einem Zeichenvorrat zusammengesetzt werden können. Anwendung finden formale Sprachen in der Linguistik, der Logik und der theoretischen Informatik. Formale Sprachen eignen… …   Deutsch Wikipedia

  • formale Bildung — formale Bildung,   aus der pädagogischen Fachsprache des 19. Jahrhunderts stammende umstrittene Formel, die das Konzept einer allgemeinen Schulung des Verstandes und Denkens besonders durch (alte) Sprachen, Grammatik und Mathematik bezeichnet; v …   Universal-Lexikon

  • Grammatik — Allegorische Darstellung der Grammatik, ihre Disziplinen als Armeen. Aus Antoine Furetières Nouvelle Allegorique, Ou Histoire Des Derniers Troubles Arrivez Au Royaume D’Eloquence (1659). Die Grammatik (Sprachlehre, griechisch [τέχνη] γραμματική,… …   Deutsch Wikipedia

  • Kontext-sensitive Grammatik — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Typ-0-Grammatik — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia