imported>PaulT: /* Definition */ nicht immer wieder verlinken

2025-03-04T21:37:48Z

Definition: nicht immer wieder verlinken

Neue Seite

'''Formale Grammatiken''' sind [[Mathematisches Modell|mathematische Modelle]] von [[Grammatik]]en, die zur eindeutigen Erzeugung und Beschreibung [[Formale Sprache|formaler Sprachen]] dienen. Sie werden in der [[Theoretische Informatik|theoretischen Informatik]], insbesondere in der [[Berechenbarkeitstheorie]], und im [[Compilerbau]] zum einen angewendet, um eindeutig festzulegen, ob ein [[Wort (Theoretische Informatik)|Wort]] Element einer Sprache ist und zum anderen, um Eigenschaften dieser formalen Sprachen zu untersuchen bzw. zu beweisen. Formale Grammatiken werden mithilfe von [[Semi-Thue-System|Semi-Thue-Systemen]] angegeben in der [[Chomsky-Hierarchie]] klassifiziert.

== Beschreibung ==
Mit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol <math>S</math> (auch ''Startvariable'' genannt) [[Produktionsregel]]n aus einer Regelmenge <math>P</math> anwenden, die aus dem Startsymbol neue Zeichenfolgen ([[Wort (Theoretische Informatik)|Wörter]]) erzeugen, welche wiederum weiter ersetzt werden können. Diesen Vorgang nennt man auch [[Ableitung (Informatik)|Ableitung]].

Das Vokabular <math>V</math> einer Grammatik, bestehend aus der [[disjunkt]]en Vereinigung eines [[Alphabet (Informatik)|Alphabets]] <math>T</math> von [[Terminalsymbol]]en mit einer Menge von [[Nichtterminalsymbol]]en <math>N</math>, 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äß [[Geordnetes Paar|geordnete Paare]] <math>(\alpha,\beta)</math>, die auch <math>\alpha \rightarrow \beta</math> geschrieben werden. Man wendet sie auf eine Zeichenfolge <math>w</math> an, indem ein Vorkommen der Zeichenfolge <math>\alpha</math> in <math>w</math> durch <math>\beta</math> ersetzt wird. Auf der linken Seite der Regel muss immer mindestens ein Nichtterminalsymbol stehen. Eine Menge von Regeln mit gleicher linker Seite, also <math>\alpha \rightarrow \beta_1,\; \ldots, \alpha \rightarrow \beta_n</math>, wird abkürzend auch als <math>\alpha \rightarrow \beta_1 \;|\; \ldots \;|\; \beta_n</math> geschrieben.

Zum Beispiel kann man mit der Regelmenge <math>X\rightarrow +\;|\;-</math> die Zeichenfolge <math>1X2</math> entweder zu <math>1+2</math> oder zu <math>1-2</math> 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 wird dargestellt durch das 4-[[Tupel]] <math>G = (V, T, P, S)</math>, worin:<ref>{{Literatur |Autor=Peter Bachmann |Titel=Grundlagen der Theoretischen Informatik |Ort=Cottbus |Datum=2001 |Seiten=47 |Kommentar=Vorlesungsskript |Online=http://www.informatik.tu-cottbus.de/~wwwpscb/lehre/GTI/vorl/skript.pdf |Format=PDF |KBytes= |Abruf=2011-02-12}}</ref>
* <math>V</math>, einer endlichen Menge von ''Symbolen'', welche als ''Symbolmenge'' oder ''Vokabular'' bezeichnet wird,
* <math>T \subset V</math>, einer Teilmenge von <math>V</math>, auch ''[[Alphabet (Informatik)|Alphabet]]'' genannt und deren Elemente ''[[Terminalsymbol]]e'' heißen,
* <math>P \subset \left( V^* \setminus T^* \right) \times V^*</math>, einer endlichen Menge von [[Produktionsregel]]n, sowie
* <math>S\in V\setminus T</math>, dem ''Startsymbol''.

Das 4-[[Tupel]] wird je nach Konvention auch so definiert, dass <math>V</math> der Menge der ''Nichtterminalsymbole'' entspricht, sodass <math>V \cap T = \emptyset</math> ist.<ref>{{Literatur |Autor=Christian Wagenknecht, Michael Hielscher |Titel=Formale Sprachen, Abstrakte Automaten und Compiler |Verlag=Springer Vieweg |Ort=Wiesbaden |Datum=2014 |Seiten=28 |DOI=10.1007/978-3-658-02692-9}}</ref>

Hierbei bezeichnet <math>X^*</math> die [[Kleenesche Hülle]] einer Menge <math>X</math> von Zeichen (oder auch Wörtern).

Die Menge <math>N = V\setminus T</math> ist die Menge von ''Nichtterminalsymbolen'' (auch ''Nonterminale'' oder ''Metasymbole'' genannt), insbesondere gehört das Startzeichen zu ihr. Das Wort auf der linken Seite der Regelpaare darf nicht ausschließlich aus Terminalzeichen bestehen, was man auch durch eine [[Formale Sprache#Konkatenation|Konkatenation]] ausdrücken kann:
:<math>\left( V^* \setminus T^* \right) = V^*NV^*</math>.

Es ergibt wenig Sinn, wenn das Wort auf der rechten Seite das Startsymbol enthält. Manche Autoren berücksichtigen das, indem sie die zugehörige Menge entsprechend beschränken, d. h. <math>V^*</math> durch <math>(V \setminus \{S\})^*</math> ersetzen.

Manche Autoren bezeichnen alternativ das Quadrupel <math>(N, T, P, S)</math> als Grammatik <math>G</math>. Es finden sich darüber hinaus folgende abweichenden Bezeichnungen:<ref>Während die Bedeutung von <math>T, N</math> und <math>\epsilon</math> bzw. <math>\lambda</math> im gegebenen Fall jeweils klar ist, muss man sich bei <math>V</math> (ebenso wie dem häufig benutzten <math>\Sigma</math>) durch Überprüfung des Kontexts klarmachen, was gemeint ist; wobei man sich auf das Grammatik-Quadrupels '''nicht''' verlassen kann.</ref>
* <math>\Sigma</math> für die ''Terminalzeichen'', hier <math>T</math>,
* <math>\Sigma</math> für das gesamte ''Vokabular'' (''Symbolmenge'') aller ''Symbole'', hier <math>V</math>,
* <math>V</math> für die Nichtterminalzeichen (''Variablen''), hier <math>N</math>,<ref name="KR1994">Klaus Reinhardt: {{Webarchiv |url=http://users.informatik.uni-halle.de/~ahyjb/dis.pdf |text=Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen |wayback=20180117143012 |archiv-bot=2019-04-11 10:04:42 InternetArchiveBot}}, Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994. Das Grammatik-Quadrupel ist hier wörtlich mit <math>(V,\Sigma,P,S)</math> angegeben, damit ist in der hier gewählten Bezeichnungsweise <math>(N,T,P,S)</math> gemeint.</ref>
* <math>\lambda</math> für das leere Wort, hier <math>\epsilon</math>.<ref name="KR1994" />

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

:<math>\rightsquigarrow\;:=\;\{(u \circ R \circ v, u \circ Q \circ v) | (R,Q)\in P, u,v\in V^*\}</math>,
wobei hier <math>\circ</math> die [[Formale Sprache#Konkatenation|Konkatenation]] von Wörtern bezeichnet.

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

Nun ist die von der Grammatik <math>G</math> erzeugte formale Sprache <math>L(G)</math> 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:

<math>L \left( G \right) := \left\{ w \in T^* | S \rightsquigarrow_G^* w \right\}</math>

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 <math>w</math> aus <math>S</math> abzuleiten. Zwei Grammatiken <math>G_1</math> und <math>G_2</math> sind genau dann [[Äquivalenzrelation|äquivalent]], wenn die durch <math>G_1</math> und <math>G_2</math> erzeugten Sprachen gleich sind:

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

Wenn alle Terminalzeichen in den Wörtern der formalen Sprachen vorkommen, dann müssen die Terminalzeichen übereinstimmen. Die Nichtterminalzeichen sind dagegen völlig frei.

== Beispiele ==
<math>G_1</math> sei eine Grammatik mit den Terminalsymbolen <math>\{a, b\}</math>, den Nichtterminalsymbolen <math>\{S, A, B\}</math>, dem Startsymbol <math>S</math> und mit den Regeln
:<math>
\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}
</math>

Dabei ist <math>\varepsilon</math> das [[Leeres Wort|leere Wort]], welches ein Wort der Länge 0 ist. Diese Grammatik <math>G_1</math> definiert die Sprache aller Wörter der Form <math>a^n b^n</math> mit <math>n \in \mathbb N_0</math>. So sind auf Grund der folgenden Ableitungen die Wörter <math>\varepsilon</math>, <math>ab</math> und <math>aabb</math> Elemente der durch <math>G_1</math> beschriebenen Sprache:
* <math>S\rightsquigarrow\varepsilon</math>, mittels Regel (2),
* <math>S\rightsquigarrow ABS\rightsquigarrow Ab\rightsquigarrow ab</math>, mittels der Regeln (1), (4) und (6),
* <math>S\rightsquigarrow ABS\rightsquigarrow ABABS\rightsquigarrow ABAb\rightsquigarrow AABb\rightsquigarrow AAbb\rightsquigarrow Aabb\rightsquigarrow aabb</math>, mittels der Regeln (1),(1),(4),(3), (5), (6) und (7).

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

Eine weitere Grammatik, die dieselbe Sprache beschreibt, ist die [[Kontextfreie Grammatik|kontextfreie]] Grammatik <math>G_2</math> mit den Regeln:
<math>\begin{matrix}S&\to&aSb\ |\ \varepsilon\end{matrix}</math>

Jede [[Rekursive Aufzählbarkeit|rekursiv aufzählbare]] Sprache wird von mehreren (und zwar [[Abzählbarkeit|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: [[Phrasenstrukturgrammatik]]en sind uneingeschränkte formale Grammatiken.
* Typ-1-Grammatiken: [[Kontextsensitive Grammatik]]en 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 [[Kontextfreie Grammatik|kontextfreien Grammatiken]] darf dagegen auf den linken Seiten der Regeln jeweils nur genau ein Nichtterminalsymbol stehen. Das Symbol kann dann unabhängig vom Kontext ersetzt werden.
* Typ-3-Grammatiken: Bei [[Reguläre Grammatik|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 (Bsp.: <math>X \to Ya</math>). Bei rechtsregulären Grammatiken darf hingegen die rechte Seite aus höchstens einem Terminalsymbol bestehen, dem höchstens ein Nichtterminal folgt (Bsp.: <math>X \to aY </math>).

Die zugehörigen Sprachklassen sind abnehmend umfangreich. Es besteht folgende echte [[Teilmenge|Inklusionsbeziehung]]:

Für die Sprachklassen <math>L_n</math> von Typ <math>n</math> mit <math>n \in \{0, 1, 2, 3\}</math> gilt: <math>L_3 \subset L_2 \subset L_1 \subset L_0</math>.

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

== Siehe auch ==
* [[Graphgrammatik]]
* [[Backus-Naur-Form]] und [[Erweiterte Backus-Naur-Form]]
* [[Syntaxtheorie]] zu (formalen) Grammatiken in der [[Linguistik]]
* [[Kommunizierendes Grammatik-System]]

== Literatur ==
* {{Literatur
|Autor=Katrin Erk, Lutz Priese
|Titel=Theoretische Informatik. Eine umfassende Einführung
|Auflage=2. erweiterte
|Verlag=Springer-Verlag
|Ort=Berlin u. a.
|Datum=2002
|ISBN=3-540-42624-8
|Seiten=53–61}}

== Weblinks ==
* [http://www.grundstudium.info/theorie/node38.php Website zum Thema Grammatik]

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4154991-0}}

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Compilerbau]]

Formale Grammatik - Versionsgeschichte

imported>PaulT: /* Definition */ nicht immer wieder verlinken