Mit Google fortfahren
Wenn du eine E-Mail-Adresse, eine Rechenaufgabe oder ein kleines Programm schreibst, müssen die Zeichen in einer passenden Reihenfolge stehen. Ein Computer kann nicht raten, was gemeint ist. Er braucht genaue Regeln. Genau dafür benutzt die Informatik Grammatiken.
- Du erklärst, was eine Grammatik in der Informatik ist.
- Du unterscheidest Terminale, Nichtterminale, Startsymbol und Produktionsregeln.
- Du leitest einfache Wörter Schritt für Schritt ab.
- Du erkennst, warum Grammatiken formale Sprachen beschreiben.
- Du ordnest reguläre Grammatiken grob in die Chomsky-Hierarchie ein.
Wozu Grammatiken in der Informatik da sind
Im Deutschunterricht beschreibt Grammatik, wie Wörter zu sinnvollen Sätzen werden. In der Informatik geht es ähnlich zu, aber viel genauer. Dort beschreibt eine Grammatik, welche Zeichenketten erlaubt sind.
Eine Zeichenkette ist eine endliche Folge von Zeichen. Zum Beispiel ist 0011 eine Zeichenkette aus den Zeichen 0 und 1. Ein Wort ist in der theoretischen Informatik ebenfalls eine Zeichenkette über einem festgelegten Zeichenvorrat.
Eine formale Sprache ist eine Menge von Wörtern, die nach festen Regeln erlaubt sind. Zum Beispiel kann eine Sprache alle Wörter enthalten, die nur aus Nullen und Einsen bestehen und mit einer Null anfangen.
Eine Grammatik in der Informatik ist ein Regelsystem, das Wörter einer formalen Sprache erzeugt oder beschreibt.
Stell dir eine Mini-Sprache für Ampelfarben vor.
Erlaubte Wörter sollen sein:
rotgelbgruen
Dann beschreibt die Grammatik nicht die Bedeutung der Farben. Sie beschreibt nur, welche Wörter korrekt aufgebaut sind.
Eine Grammatik fragt nicht zuerst: Was bedeutet das Wort? Sie fragt: Darf dieses Wort nach den Regeln entstehen?
Interaktive Quizfrage wird geladen ...
Die Bausteine einer Grammatik
Eine Grammatik besteht aus mehreren Teilen. Du kannst sie dir wie einen Baukasten vorstellen. Manche Teile sind fertige Zeichen, andere sind Platzhalter, die noch ersetzt werden müssen.
Ein Terminalsymbol ist ein Zeichen, das am Ende im fertigen Wort stehen darf. Es wird nicht weiter ersetzt. Bei einer Sprache über 0 und 1 sind 0 und 1 typische Terminalsymbole.
Ein Nichtterminalsymbol ist ein Hilfssymbol. Es steht nur während der Erzeugung da und muss noch ersetzt werden. Oft schreibt man Nichtterminale als Großbuchstaben, zum Beispiel S, A oder B.
Das Startsymbol ist das Nichtterminal, mit dem jede Erzeugung beginnt. Meist heißt es S. Eine Produktionsregel gibt an, wodurch ein Symbol oder eine Symbolfolge ersetzt werden darf.
Eine Grammatik wird oft als \(G=(N,T,P,S)\) geschrieben.
Dabei bedeutet:
- \(N\): Menge der Nichtterminalsymbole
- \(T\): Menge der Terminalsymbole
- \(P\): Menge der Produktionsregeln
- \(S\): Startsymbol
Eine sehr einfache Grammatik kann so aussehen:
\(N=\{S\}\)
\(T=\{0,1\}\)
\(S\) ist das Startsymbol.
Regeln:
\(S \rightarrow 0S\)
\(S \rightarrow 1\)
Diese Grammatik beginnt bei S. Sie kann beliebig viele Nullen erzeugen und endet dann mit einer Eins.
Terminale sind fertig. Nichtterminale sind Platzhalter. Das Startsymbol ist der erste Platzhalter.
Interaktiver Lückentext wird geladen ...
Produktionsregeln und Ableitungen
Eine Produktionsregel sieht oft so aus: \(A \rightarrow x\). Das bedeutet: Wenn links A steht, darfst du es durch das ersetzen, was rechts steht.
Eine Ableitung ist eine Folge solcher Ersetzungen. Du startest mit dem Startsymbol. Dann wendest du Regeln an, bis kein Nichtterminal mehr übrig ist. Erst dann hast du ein fertiges Wort der Sprache.
Nimm diese Grammatik:
\(S \rightarrow 0S\)
\(S \rightarrow 1\)
Wir leiten das Wort 001 ab:
\(S \rightarrow 0S\)
\(0S \rightarrow 00S\)
\(00S \rightarrow 001\)
Am Ende stehen nur noch Terminale. Also gehört 001 zur Sprache dieser Grammatik.
Das Zeichen \(\epsilon\) steht für das leere Wort. Es bedeutet: Es wird kein Zeichen erzeugt. Das ist nützlich, wenn eine Ableitung enden darf, ohne noch ein weiteres Terminal anzuhängen.
Mit den Regeln
\(S \rightarrow 0S\)
\(S \rightarrow \epsilon\)
kannst du 000 erzeugen:
\(S \rightarrow 0S \rightarrow 00S \rightarrow 000S \rightarrow 000\)
Die letzte Regel entfernt das übrig gebliebene S, weil \(\epsilon\) kein sichtbares Zeichen ist.
Eine Ableitung ist wie ein Umbau in mehreren Schritten: Du ersetzt Platzhalter, bis nur noch fertige Zeichen übrig sind.
Interaktive Quizfrage wird geladen ...
Die erzeugte Sprache
Eine Grammatik erzeugt meist nicht nur ein Wort, sondern viele Wörter. Die erzeugte Sprache einer Grammatik ist die Menge aller fertigen Wörter, die aus dem Startsymbol abgeleitet werden können.
Wichtig ist: Zwischenschritte zählen nicht zur Sprache, wenn sie noch Nichtterminale enthalten. Nur Wörter aus Terminalsymbolen zählen.
Die Grammatik hat die Regeln:
\(S \rightarrow 0S\)
\(S \rightarrow 1\)
Mögliche Ableitungen sind:
\(S \rightarrow 1\)
\(S \rightarrow 0S \rightarrow 01\)
\(S \rightarrow 0S \rightarrow 00S \rightarrow 001\)
Die erzeugte Sprache enthält also 1, 01, 001, 0001 und so weiter.
Die von einer Grammatik erzeugte Sprache ist die Menge aller Terminalwörter, die sich aus dem Startsymbol ableiten lassen.
Das Zwischenwort 00S gehört nicht zur erzeugten Sprache. Es enthält noch das Nichtterminal S.
Das fertige Wort 001 gehört dazu. Es enthält nur noch Terminale.
Zur Sprache gehören nur fertige Wörter. Zwischenschritte sind nur der Weg dorthin.
Interaktiver Lückentext wird geladen ...
Reguläre Grammatiken
Manche Grammatiken sind stark eingeschränkt. Das macht sie einfacher zu untersuchen. Eine reguläre Grammatik ist eine Grammatik, deren Regeln nur sehr einfache Formen haben.
Bei einer rechtslinearen regulären Grammatik steht rechts höchstens ein Nichtterminal, und wenn es vorkommt, dann ganz am Ende. Typische Formen sind zum Beispiel \(A \rightarrow aB\), \(A \rightarrow a\) oder \(A \rightarrow \epsilon\).
Reguläre Grammatiken erzeugen reguläre Sprachen. Diese Sprachen können auch von endlichen Automaten erkannt werden. Ein endlicher Automat ist ein Modell, das ein Wort Zeichen für Zeichen liest und dabei zwischen endlich vielen Zuständen wechselt.
Diese Grammatik erzeugt Wörter mit einer geraden Anzahl von Einsen:
\(E \rightarrow 1O\)
\(E \rightarrow \epsilon\)
\(O \rightarrow 1E\)
Startsymbol ist E.
Ableitung von 11:
\(E \rightarrow 1O \rightarrow 11E \rightarrow 11\)
Ableitung von 1111:
\(E \rightarrow 1O \rightarrow 11E \rightarrow 111O \rightarrow 1111E \rightarrow 1111\)
Die Namen E und O kannst du dir so merken: E steht hier für gerade, O für ungerade. Nach jeder erzeugten Eins wechselt die Grammatik zwischen beiden Zuständen.
Reguläre Grammatiken bauen Wörter besonders schrittweise: meist ein Terminal pro Schritt und höchstens ein Hilfssymbol für den Rest.
Interaktive Quizfrage wird geladen ...
Grammatikklassen und Chomsky-Hierarchie
Nicht jede Grammatik ist regulär. Manche Sprachen brauchen stärkere Regeln. Deshalb ordnet die theoretische Informatik Grammatiken in Klassen ein.
Die Chomsky-Hierarchie ist eine Einteilung formaler Grammatiken nach der Stärke ihrer Produktionsregeln. Je höher die Ausdrucksstärke, desto mehr Sprachen kann die Klasse beschreiben. Gleichzeitig wird die automatische Verarbeitung oft schwieriger.
Die wichtigsten Klassen sind:
Interaktive Lernkarten wird geladen ...
Eine kontextfreie Grammatik ist eine Grammatik, bei der links in jeder Regel genau ein Nichtterminal steht. Solche Grammatiken können zum Beispiel Klammerstrukturen beschreiben, etwa korrekt geschachtelte Klammern.
Eine kontextsensitive Grammatik darf Regeln nutzen, bei denen die Umgebung eines Symbols wichtig ist. Eine allgemeine Grammatik hat die wenigsten Einschränkungen.
Die Sprache mit gleich vielen Nullen und Einsen in der Form 0...01...1, also zum Beispiel 01, 0011 und 000111, ist nicht regulär. Ein endlicher Automat kann sich nicht beliebig viele Nullen merken.
Eine kontextfreie Grammatik kann sie aber beschreiben:
\(S \rightarrow 0S1\)
\(S \rightarrow \epsilon\)
Damit entstehen außen immer passend eine Null und eine Eins.
Regulär ist die einfachste wichtige Klasse. Kontextfrei ist stärker und kann zum Beispiel passende Paare wie Klammern oder gleiche Anzahlen modellieren.
Interaktive Quizfrage wird geladen ...
Zusammenfassung
Eine Grammatik in der Informatik ist ein genaues Regelsystem für formale Sprachen. Sie arbeitet mit Terminalsymbolen, Nichtterminalsymbolen, einem Startsymbol und Produktionsregeln.
Mit einer Ableitung ersetzt du Schritt für Schritt Nichtterminale. Ein Wort gehört erst dann zur erzeugten Sprache, wenn es nur noch aus Terminalsymbolen besteht.
Reguläre Grammatiken sind besonders einfache Grammatiken. Sie erzeugen reguläre Sprachen und passen eng zu endlichen Automaten.
Die Chomsky-Hierarchie ordnet Grammatiken nach ihrer Stärke. Typ 3 ist regulär, Typ 2 ist kontextfrei, Typ 1 ist kontextsensitiv und Typ 0 ist allgemein.
Wenn du Grammatiken prüfst, stelle dir immer drei Fragen: Womit starte ich? Welche Ersetzungen sind erlaubt? Welche fertigen Wörter können am Ende entstehen?