Formale Grammatik

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Beschreibung[Bearbeiten | Quelltext bearbeiten]

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

Das Vokabular einer Grammatik, bestehend aus Terminalsymbolen und Nichtterminalsymbolen , 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 geschrieben werden. Man wendet sie auf eine Zeichenfolge an, indem ein Vorkommen der Zeichenfolge in durch ersetzt wird. Auf der linken Seite der Regel muss immer mindestens ein Nichtterminalsymbol stehen. Eine Menge von Regeln mit gleicher linker Seite, also , wird abkürzend auch als geschrieben.

Zum Beispiel kann man mit der Regelmenge die Zeichenfolge entweder zu oder zu 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[Bearbeiten | Quelltext bearbeiten]

Eine formale Grammatik ist ein 4-Tupel bestehend aus:[1]

  • , einer endlichen Menge, welche als Vokabular und deren Elemente als Nonterminale bzw. Metasymbolen' bezeichnet werden,
  • , eine endliche Menge, die Alphabet genannt wird und deren Elemente Terminalsymbole heißen,
  • , einer endlichen Menge von Produktionsregeln, sowie
  • , dem Startsymbol.

Es muß gelten

Hierbei bezeichnet die Kleenesche Hülle von .

Die von einer Grammatik beschriebene Sprache[Bearbeiten | Quelltext bearbeiten]

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

.

Gibt es nun eine Folge von Wörtern , bei der gilt, dass für jede natürliche Zahl mit das Wort in übergeht (), so ist in Schritten aus ableitbar, was durch dargestellt wird. Eine solche Wortfolge wird Ableitung oder Rechnung von in der Länge genannt. Weiterhin heißt in ableitbar, wenn es mindestens ein gibt, so dass in Schritten aus ableitbar ist. Wenn in ableitbar ist, so wird dies durch die Schreibweise dargestellt. Dabei wird zusätzlich definiert, dass für jedes Wort gilt, dass ist, so dass die Relation die reflexiv-transitive Hülle der Relation ist.

Nun ist die von der Grammatik erzeugte formale Sprache 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:

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 aus abzuleiten. Zwei Grammatiken und sind genau dann äquivalent, wenn die durch und erzeugten Sprachen gleich sind:

Beispiele[Bearbeiten | Quelltext bearbeiten]

sei eine Grammatik mit den Terminalsymbolen , den Nichtterminalsymbolen , dem Startsymbol und mit den Regeln

Dabei ist das leere Wort, welches ein Wort der Länge 0 ist. Diese Grammatik definiert die Sprache aller Wörter der Form mit . So sind auf Grund der folgenden Ableitungen die Wörter , und Elemente der durch beschriebenen Sprache:

  • , mittels Regel (2),
  • , mittels der Regeln (1), (4) und (6),
  • , mittels der Regeln (1),(1),(4),(3), (5), (6) und (7).

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

Eine weitere Grammatik, die dieselbe Sprache beschreibt, ist die kontextfreie Grammatik mit den Regeln:

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Die Chomsky-Hierarchie teilt die Grammatiken nach der Art der Produktionsregeln in Klassen vom Typ 0 bis Typ 3 ein:

  • Typ-0-Grammatiken: Phrasenstrukturgrammatiken sind uneingeschränkte formale Grammatiken.
  • Typ-1-Grammatiken: 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.
  • Typ-2-Grammatiken: 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.
  • Typ-3-Grammatiken: Bei regulären Grammatiken enthalten die linken Seiten der Regeln ebenfalls nur genau ein Nichtterminalsymbol. Bei linksregulären Grammatiken darf die rechte Seite der Regel aus höchstens einem Nichtterminalsymbol bestehen, dem höchstens ein Terminalsymbol folgt. Bei rechtsregulären Grammatiken darf hingegen die rechte Seite aus höchstens einem Terminalsymbol bestehen, dem höchstens ein Nichtterminal folgt.

Die zugehörigen Sprachklassen sind abnehmend umfangreich. Es besteht folgende echte Inklusionsbeziehung:

Für die Sprachklassen von Typ mit gilt: .

Weitere Sprachklassen[Bearbeiten | Quelltext bearbeiten]

Von der Chomsky-Hierarchie abgesehen haben sich weitere Klassen an Grammatiken etabliert:

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

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