imported>TimoHartmannn am 10. März 2026 um 16:04 Uhr

2026-03-10T16:04:08Z

Neue Seite

{{Belege}}

Eine '''Produktionsregel''' (auch '''Regel''', '''Produktion''' oder '''Ersetzungsregel''' genannt) ist in der Theorie [[Formale Grammatik|formaler Grammatiken]] eine Regel, die angibt, wie aus [[Wort (Theoretische Informatik)|Wörtern]] durch eine Grammatik neue Wörter bzw. Symbolfolgen [[Ableitung (Informatik)|produziert]] werden.

== Definition ==
Formal ist eine Produktionsrege<ref>{{Internetquelle |url=https://hpi.de/friedrich/teaching/units/grammatiken.html |titel=Grammatiken |abruf=2026-03-10}}</ref>l <math>p</math> aus einer Grammatik <math>G=(V,T,P,S)</math> - mit ''Vokabular'' <math>V</math>, [[Alphabet (Informatik)|Alphabet]] <math>T</math> von ''[[Terminalsymbol]]en'', ''Regelmenge'' <math>P</math> und ''[[Startsymbol]]'' <math>S</math> - ein Element der Regelmenge, also <math>p \in P</math>.<ref>Die Mitglieder der Menge <math>N := V \setminus T</math> bezeichnet man als ''[[Nichtterminalsymbol|Nichtterminalzeichen]]'', zu diesen gehört das Startzeichen, also <math>S \in N</math>.</ref>

Eine Regel ist ein [[geordnetes Paar]] <math>p = (\alpha,\beta) \in P</math> der beiden Wörter <math>\alpha</math> und <math>\beta</math>, wenn <math>\alpha</math> ein Wort aus [[Differenzmenge|<math>V^* \setminus T^*</math>]] ist und <math>\beta</math> ein Wort aus <math>V^*</math> ist. Das Wort <math>\alpha</math> kann also eine beliebig lange Folge von Zeichen des Vokabulars <math>V</math> sein (<math>V^*</math> ist die [[Kleenesche und positive Hülle|Kleenesche Hülle]] von <math>V</math>), solange sie nicht leer ist und nicht nur aus Terminalsymbolen <math>s \in T</math> besteht. Es ist daher <math>V^* \setminus T^* =</math>[[Konkatenation (Formale Sprache)|<math>V^*NV^*</math>]]. Das Wort <math>\beta</math> kann dann gemäß der Regel das Wort <math>\alpha</math> ersetzen und kann eine beliebig lange, endliche Folge von Zeichen des Vokabulars sein. Insbesondere kann <math>\beta</math> auch nur aus Terminalsymbolen bestehen (<math>\beta \in T^*</math>) oder das [[Leeres Wort|leere Wort]] sein (<math>\beta=\varepsilon</math>). Damit stellen die Produktionsregeln eine endliche Teilmenge des [[Kartesisches Produkt|kartesischen Mengenprodukts]]
:<math>(V^* \setminus T^*) \times V^* = V^*NV^* \times V^*</math>,
also eine [[Relation (Mathematik)|Relation]] dar. Verlangt man noch, dass auf der rechten Seite einer Regel keine Startzeichen vorkommen dürfen, dann hat im obigen kartesischen Produkt auf der rechten Seite jeweils <math>(V\setminus\{ S \})^*</math> statt <math>V^*</math> zu stehen.<ref name="KR1994">Sinngemäß nach Klaus Reinhardt: [http://users.informatik.uni-halle.de/~ahyjb/dis.pdf Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen], Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994.</ref>

Eine Regel <math>p = (\alpha,\beta)</math> wird oftmals durch die Schreibweise <math>\alpha \rightarrow \beta</math> (mit dem Relationszeichen <math>\rightarrow</math> anstelle von <math>P</math>) dargestellt, und zu jedem festen <math>\alpha</math> kann die Gesamtheit zugehöriger Regeln <math>\alpha \rightarrow \beta_1,\; \alpha \rightarrow \beta_2,\; \alpha \rightarrow \beta_3, \ldots</math> durch die Schreibweise <math>\alpha \rightarrow \beta_1 \;|\; \beta_2 \;|\; \beta_3 \;| \ldots</math> abgekürzt werden.<ref>Vergleiche [[Backus-Naur-Form]].</ref>

== Anwendung von Produktionsregeln ==
In der [[Theoretische Informatik|Theoretischen Informatik]] sowie in der [[Sprachwissenschaft|Linguistik]] werden die Produktionsregeln einer formalen Grammatik angewendet, um formale Sprachen zu beschreiben oder zu erzeugen.

Liegt ein Wort <math>v_1\alpha v_2 = v \in V^+</math> vor, so lässt sich eine Produktionsregel <math>(\alpha,\beta)</math> auf <math>v</math> anwenden, mit dem resultierenden Wort <math>v_1\beta v_2</math>. Ein Wort, das nur aus Terminalsymbolen besteht und vom Startsymbol abgeleitet werden kann, ist ein Wort der Sprache, die von der Grammatik beschrieben wird.

== Beispiele ==
Es sei innerhalb einer formalen Grammatik mit den Nichtterminalsymbolen <math>N = \{ A, B \}</math> und den Terminalsymbolen <math>T = \{ a, b \}</math> die Produktionsregel <math>aBa \rightarrow bA</math> definiert. Durch Anwendung dieser Regel kann bei der Erzeugung der durch die Grammatik beschriebenen Sprache zum Beispiel das Wort <math>aBaBaBA</math> zum Wort <math>bABaBA</math> abgeleitet werden, wobei hier das [[Präfix (Theoretische Informatik)|Präfix]] <math>aBa</math> durch die Konklusion <math>bA</math> ersetzt wird. Es wäre jedoch nach der Definition formaler Grammatiken auch möglich, das zweite Vorkommen des Wortes <math>aBa</math> zu ersetzen, so dass das Wort <math>aBbABA</math> entsteht.

Wäre außerdem die Regel <math>aBa \rightarrow \varepsilon</math> definiert, so könnte das zuvor betrachtete Wort <math>aBaBaBA</math> außerdem in die Wörter <math>BaBA</math> bzw. <math>aBBA</math> abgeleitet werden. (<math>\varepsilon</math> ist die in der Regel verwendete Notation für das [[leeres Wort|leere Wort]], ein Wort, das aus keinem einzigen Zeichen besteht.)

== Informatik ==
Wie bereits beschrieben, stellen Produktionsregeln einen grundlegenden Bestandteil formaler Grammatiken dar und werden demnach dazu verwendet, um formale Sprachen zu beschreiben. So werden Produktionsregeln etwa im Rahmen des [[Compilerbau]]s dazu verwendet, um eine [[Programmiersprache]] zu beschreiben. Produktionsregeln werden hier häufig in der [[Backus-Naur-Form]] dargestellt.

Eine kognitive Anwendung haben Produktionsregeln in [[Regelbasiertes System|regelbasierten Systemen]]: Hier spricht man von Produktionsregeln, wenn die Konklusionen der Regeln, mit denen das System arbeitet, nur aus Konjunktionen von Literalen bestehen.

== Linguistik ==
In der Theorie der [[Transformationsgrammatik]] veranschaulichen Produktionsregeln, die hier '''Phrasenstrukturregeln''' ('''PS-Regel'''n) genannt werden, den Gedanken, dass ein [[Satz (Grammatik)|Satz]] eine grammatische Struktur besitzt, die aus kategorietragenden Bestandteilen [[Rekursion|rekursiv aufgebaut]] ist. Die ersten und klassisch gewordenen PS-Regeln in [[Noam Chomsky]]s Buch "Syntactic Structures" lauten:

S → NP VP (ein Satz besteht aus einer [[Nominalphrase]] und einer [[Verbalphrase]])
VP → V NP*　(eine Verbalphrase besteht aus einem Verb und null bis vielen Nominalphrasen)

== Anmerkungen und Einzelnachweise ==
<references />

== Weblinks ==
{{Wiktionary|Phrasenstrukturregel}}

[[Kategorie:Theorie formaler Sprachen]]

Produktionsregel - Versionsgeschichte

imported>TimoHartmannn am 10. März 2026 um 16:04 Uhr