Formale Grammatik

Eine formale Grammatik G ist gegeben durch ein 4-Tupel, bestehend aus

• einer endlichen Menge N von Nichtterminalsymbolen (im Folgenden kurz Nichtterminale, oft aber auch Variablen genannt)
• einer endlichen Menge Σvon Terminalsymbolen (im Folgenden kurz Terminale genannt) (wobei das Alphabet Σund die Nichtterminale N disjunkt sind)
• einer endlichen Menge P von Produktionsregeln (im Folgenden kurz Regeln, oft auch Produktionen, genannt)
• einem Startsymbol S, welches zu den Nichtterminalen gehört.

Formal: G = (N, Σ, P, S), S ∈ N, N ∩ Σ= ∅

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

Produktionsregeln

Eine Regel besteht aus einer linken (Prämisse) und einer rechten Seite (Konklusion), die jeweils ein Wort bestehend aus Terminalen und Nichtterminalen sind. Die linke Seite muss mindestens ein Nichtterminal beinhalten und die rechte Seite kann dabei im Gegensatz zur linken Seite auch das leere Wort (im folgenden mit εbezeichnet) sein, also das Wort der Länge Null.

Eine Regel kann auf ein Wort, bestehend aus Terminalen und Nichtterminalen, angewendet werden, wobei ein beliebiges Vorkommen der linken Seite der Regel im Wort durch die rechte Seite der Regel ersetzt wird.

Man schreibt Produktionen in der Form A → w, was bedeutet, dass das Nicht-Terminalsymbol A durch die Zeichenfolge w ersetzt werden darf. Eine Folge von Anwendungen von Produktionsregeln bezeichnet man als Ableitung .

Beispiele für Produktionen sind:

• A → a
• A → Aa
• B → Ab
• C → Bcc

Aufgrund dieser Regeln können dann gültige Texte produziert werden. Nimmt man C als Startsymbol, so ergibt sich zum Beispiel die folgende Ableitung:

C ⇒ Bcc ⇒Abcc ⇒Aabcc ⇒Aaabcc ⇒... ⇒aaaaabcc

Der obenstehende Text aaaaabcc kann also durch sukzessive Anwendung der Regeln aus dem Startsymbol C produziert werden (daher das Wort Produktionen). Alle Texte, die so produziert werden können, sind gültig im Sinne der formalen Grammatik.

Gültige Texte wären hier abcc, aabcc, aaabcc, ..., der Text bcbca ist dagegen ungültig.

Formale Sprache

Eine Grammatik G erzeugt eine formale Sprache L(G) die aus allen Wörtern besteht, die nur aus Terminalen bestehen und vom Startsymbol in einer endlichen Anzahl von Schritten abgeleitet werden können.

Beispiele

Wohlgeformte Klammerterme

Lässt man in einem - korrekt gebildeten - arithmetischen Term die Zahlen, Operatoren und Bezeichner weg, d.h. betrachtet man nur die Klammern, so erhält man Zeichenfolgen der Form (()), ()() oder (()()), die sogenannten wohlgeformten Klammerterme. Ein solcher Term muss gleich viele öffnende wie schließende Klammern enthalten, und an keiner Stelle darf die Anzahl der schließenden die der öffnenden Klammern überschreiten. Die Produktionsregeln zur Erzeugung wohlgeformter Klammerterme lauten wie folgt:

1. S → ()
2. S → (S)
3. S → SS

Die dritte Regel dient dazu, Klammerterme aneinanderzureihen; die zweite Regel erlaubt eine rekursive Verschachtelung von Klammern und die erste Regel gewährleistet einen Abbruch des Erzeugungsvorgangs. Die Zeichenfolge (())(()()) lässt sich durch folgende Ableitung erzeugen:

S ⇒ SS ⇒ (S)S ⇒(())(S) ⇒(())(SS) ⇒(())(()S) ⇒(())(()())

Die drei Regeln (1), (2) und (3) lassen sich auch kürzer schreiben:

S ⇒ () | (S) | SS

Das heisst, Produktionsregeln mit der gleichen linken Seite werden zu einer einzigen Regel zusammengefasst: Das Zeichen "|" bedeutet "oder".

In diesem Beispiel sind die Klammern '(' und ')' die Terminalsymbole, das Zeichen 'S' ist das einzige Nicht-Terminalsymbol, welches auch Startsymbol sein muss. Im Sinne der oben angegebenen Definition ist die Grammatik gegeben durch

G = ({"(",")"}, {S}, {S → () | (S) | SS}, S)

Ausgewogene Bitmuster

Wir betrachten die Sprache über dem Alphabet {0, 1}, bei der jedes Wort gleich viele Nullen und Einsen enthält (z.B.: 01, 10, 001011, 1000011011). Immer, wenn eine Null erzeugt ist, müssen wir uns merken, dass zum Ausgleich noch eine Eins anzufügen ist; entsprechendes gilt für die Einsen. Al Nicht-Terminalsymbole verwenden wir S, A und B, wobei S das Startzeichen ist, d.h. aus S sollen alle Wörter der Sprache abgeleitet werden können. Aus A sollen alle Wörter hergeleitet werden, die eine Eins mehr als Nullen enthalten; entsprechendes für B. Diese Überlegung führt zur Grammatik mit folgenden Produktionen:

1. S → 0A | 1B
2. A → 1 | 1S | 0AA
3. B → 0 | 0S | 1BB

Betrachten wir eine Ableitung:

S ⇒ 1B ⇒11BB ⇒11B0 ⇒110S0 ⇒1100A0 ⇒110010

Es gibt durchaus auch andere Produktionsregeln, mit denen sich genau dieselben Wörter herleiten lassen. Zum Beispiel so:

1. S → 01 | 10 | SS | 0S1 | 1S0

Das Wort 110010 wird nunmehr so hergeleitet:

S ⇒ 1S0 ⇒1SS0 ⇒1S010 ⇒110010

Zwei Grammatiken heissen äquivalent, wenn sie die gleiche formale Sprache erzeugen.

Aufgaben

Aufgabe 1

Welche formale Sprache wird von der Grammatik mit den Terminalen {a, b} und den Produktionen S → a | b | aSa | bSb erzeugt? Leiten Sie mindestens fünf Wörter her und versuchen Sie, eine charakteristische Eigenschaft aller Wörter dieser Sprache zu finden.

Aufgabe 2

Geben Sie eine Grammatik an, welche die formale Sprache {aⁿb²ⁿ | n>0} = {abb, aabbbb, aaabbbbbb, ...} erzeugt.

Aufgabe 3

Geben Sie zwei Grammatiken G₁ und G₂ der formalen Sprache an, die von obigem Automaten akzeptiert wird. Die Grammatik G₁ soll mit einem Nichtterminal auskommen, G₂ soll genau zwei Nichtterminale verwenden.

Aufgabe 4

Gegeben sei die Grammatik G₁ = (N, Σ, P, S) mit

• N = {A, S},
• Σ = {a, b},
• P = {S → aAb | aAa | bAa | bAb, A → S | ε }.

1. Geben Sie drei Wörter verschiedener Länge an, die von dieser Grammatik G₁ erzeugt werden.
2. Beschreiben Sie die von der Grammatik erzeugte Sprache L.
3. Entwickeln Sie den Zustandsgraphen eines Akzeptors, der die Zugehörigkeit eines Wortes zur Sprache L erkennt.
4. Geben Sie eine äquivalente reguläre Grammatik G₂ an, die L erzeugt.

[Anmerkung: ε ist das leere Wort.]

» drucken: pdf | html