Formale Grammatik: Definition

Formale Sprachen haben wir im Artikel zuvor schon genauer beleuchtet. Falls Du den Artikel noch nicht gelesen hast, kannst Du das hier nachholen. Formale Sprachen basieren auf den formalen Grammatiken, die wiederrum als mathematisches Regelwerk der Sprache dient. Ähnlich wie in der natürlichen Sprache, zeigt eine Grammatik, wie man syntaktisch und semantisch richtig Wörter oder Sätze bildet. So verhält sich auch die formale Grammatik gegenüber der formalen Sprache. In der theoretischen Informatik finden sie Anwendung im Compilerbau, um festzustellen, ob ein bestimmtes Wort überhaupt Bestandteil der Sprache L ist.

Definition

Die formale Grammatik G besteht aus

1. Nichtterminale N → grammatikalische Variablen
2. Terminale T → Alphabetzeichen
3. Produktionsregeln P, um neue Wörter abzuleiten
4. Startvariable s, mit s ∈ N

Beispiel formale Grammatik

Unter Definition habe ich schon mal definiert, was eine formale Grammatik benötigt. Zum besseren Verständnis möchte ich jetzt ein Beispiel dazu bilden:

G = {N, T, P, s} mit
N = {X, Y}
T = {a, b, c}
P = {X → aX, X → bcY, Y → cbY, Y → a}
s = X

(Ich habe jetzt hier nur wenige Produktionsregeln definiert, um das Beispiel einfacher zu halten)

Jetzt kann ich natürlich anfangen ein Wort zu bilden. Begonnen wird in diesem Beispiel mit X:

X → aX → abcY → abccbY → abccba

So habe ich jetzt quasi nach und nach die Nichtterminale ersetzt. Hierbei kann ich mich willkürlich für Regeln entscheiden, um Wörter zu bilden. Das Beispiel habe ich so definiert, dass ich der Reihe nach alle Nichtterminale ersetzen kann. Ein Wort ist dann gebildet, wenn ich alle Nichtterminale ersetzt habe.

Zusammenfassung

Hier nochmal eine kurze Auflistung der wesentlichen Inhalte:

• Alle Nichtterminale N sind in den Produktionregeln P zu ersetzen, um ein Wort bilden zu können
• Die Reihenfolge der angewandten Produktionregeln sind egal
• Ein Nichtterminal kann mehrere Produktionsregeln besitzen
• Statt folgender Schreibweise X → aX, X → bcY kann man auch zusammenfassend X → aX | bcY schreiben (Der Strich | steht hier für „oder“)
• Der Pfeil → steht für „ist definiert als“ oder einfach „definiert“

Ansonsten hoffe ich, dass die „trockene“ Definition klar wurde anhand des Beispiels. Bei Fragen, Anregungen oder sogar Wünschen hinterlass gerne ein Kommentar!