Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mitBelegen (beispielsweiseEinzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst undgute Belege einfügst.

EineProduktionsregel (auchRegel,Produktion oderErsetzungsregel genannt) ist in der Theorieformaler Grammatiken eine Regel, die angibt, wie ausWörtern durch eine Grammatik neue Wörter bzw. Symbolfolgenproduziert werden.

Formal ist eine Produktionsregel${\displaystyle p}$ aus einer Grammatik${\displaystyle G=(V,T,P,S)}$ - mitVokabular${\displaystyle V}$,Alphabet${\displaystyle T}$ vonTerminalsymbolen,Regelmenge${\displaystyle P}$ undStartsymbol${\displaystyle S}$ - ein Element der Regelmenge, also${\displaystyle p\in P}$.^[1]

Eine Regel ist eingeordnetes Paar${\displaystyle p=(\alpha ,\beta )\in P}$ der beiden Wörter${\displaystyle \alpha }$ und${\displaystyle \beta }$, wenn${\displaystyle \alpha }$ ein Wort aus${\displaystyle V^{\ast }\setminus T^{\ast }}$ ist und${\displaystyle \beta }$ ein Wort aus${\displaystyle V^{\ast }}$ ist. Das Wort${\displaystyle \alpha }$ kann also eine beliebig lange Folge von Zeichen des Vokabulars${\displaystyle V}$ sein (${\displaystyle V^{\ast }}$ ist dieKleenesche Hülle von${\displaystyle V}$), solange sie nicht leer ist und nicht nur aus Terminalsymbolen${\displaystyle s\in T}$ besteht. Es ist daher${\displaystyle V^{\ast }\setminus T^{\ast }=}$${\displaystyle V^{\ast }N{V}^{\ast }}$. Das Wort${\displaystyle \beta }$ kann dann gemäß der Regel das Wort${\displaystyle \alpha }$ ersetzen und kann eine beliebig lange, endliche Folge von Zeichen des Vokabulars sein. Insbesondere kann${\displaystyle \beta }$ auch nur aus Terminalsymbolen bestehen (${\displaystyle \beta \in T^{\ast }}$) oder dasleere Wort sein (${\displaystyle \beta =\epsilon }$). Damit stellen die Produktionsregeln eine endliche Teilmenge deskartesischen Mengenprodukts

${\displaystyle (V^{\ast }\setminus T^{\ast })\times V^{\ast }=V^{\ast }N{V}^{\ast }\times V^{\ast }}$,

also eineRelation 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${\displaystyle (V\setminus \{S\}{)}^{\ast }}$ statt${\displaystyle V^{\ast }}$ zu stehen.^[2]

Eine Regel${\displaystyle p=(\alpha ,\beta )}$ wird oftmals durch die Schreibweise${\displaystyle \alpha \to \beta }$ (mit dem Relationszeichen${\displaystyle \to }$ anstelle von${\displaystyle P}$) dargestellt, und zu jedem festen${\displaystyle \alpha }$ kann die Gesamtheit zugehöriger Regeln${\displaystyle \alpha \to {\beta }_1,\alpha \to {\beta }_2,\alpha \to {\beta }_3,\dots }$ durch die Schreibweise${\displaystyle \alpha \to {\beta }_1|{\beta }_2|{\beta }_3|\dots }$ abgekürzt werden.^[3]

In derTheoretischen Informatik sowie in derLinguistik werden die Produktionsregeln einer formalen Grammatik angewendet, um formale Sprachen zu beschreiben oder zu erzeugen.

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

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

Wäre außerdem die Regel${\displaystyle aBa\to \epsilon }$ definiert, so könnte das zuvor betrachtete Wort${\displaystyle aBaBaBA}$ außerdem in die Wörter${\displaystyle BaBA}$ bzw.${\displaystyle aBBA}$ abgeleitet werden. (${\displaystyle \epsilon }$ ist die in der Regel verwendete Notation für dasleere Wort, ein Wort, das aus keinem einzigen Zeichen besteht.)

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 desCompilerbaus dazu verwendet, um eineProgrammiersprache zu beschreiben. Produktionsregeln werden hier häufig in derBackus-Naur-Form dargestellt.

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

In der Theorie derTransformationsgrammatik veranschaulichen Produktionsregeln, die hierPhrasenstrukturregeln (PS-Regeln) genannt werden, den Gedanken, dass einSatz eine grammatische Struktur besitzt, die aus kategorietragenden Bestandteilenrekursiv aufgebaut ist. Die ersten und klassisch gewordenen PS-Regeln inNoam Chomskys Buch "Syntactic Structures" lauten:

S → NP VP (ein Satz besteht aus einerNominalphrase und einerVerbalphrase)VP → V NP*　(eine Verbalphrase besteht aus einem Verb und null bis vielen Nominalphrasen)

1. ↑Die Mitglieder der Menge${\displaystyle N:=V\setminus T}$ bezeichnet man alsNichtterminalzeichen, zu diesen gehört das Startzeichen, also${\displaystyle S\in N}$.
2. ↑Sinngemäß nach Klaus Reinhardt:Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen, Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994.
3. ↑VergleicheBackus-Naur-Form.

Wiktionary: Phrasenstrukturregel – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

• Theorie formaler Sprachen

• Wikipedia:Belege fehlen