Produktionsregel: Unterschied zwischen den Versionen

Version vom 27. November 2015, 13:14 Uhr

Eine Produktionsregel (auch Regel oder Produktion genannt) ist in der Theorie formaler Grammatiken eine Regel, die angibt, wie aus Wörtern durch eine Grammatik neue Wörter produziert werden.

Definition

Formal ist eine Produktionsregel p aus einer Grammatik <math>G=(V,\Sigma,P,S)</math> mit Vokabular V, Alphabet \Sigma, Regelmenge P und Startsymbol S ein Element aus P, also p \in P.

Eine Regel ist ein geordnetes Paar (\alpha,\beta) \in P der beiden Wörter \alpha und \beta, wenn \alpha ein Wort aus V^* \setminus \Sigma^* ist und \beta ein Wort aus V^* ist. Das Wort \alpha kann also eine beliebig lange Folge von Zeichen des Vokabulars V sein (V^* ist die Kleenesche Hülle von V), solange sie nicht leer ist und nicht nur aus Terminalsymbolen s \in \Sigma besteht. Das Wort \beta kann dann gemäß der Regel das Wort \alpha ersetzen und kann eine beliebig lange, endliche Folge von Zeichen des Vokabulars sein. Insbesondere kann \beta auch nur aus Terminalsymbolen bestehen (\beta \in \Sigma^*) oder das leere Wort sein (\beta=\varepsilon).

Beispiele

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

Wäre außerdem die Regel aBa \rightarrow \varepsilon definiert, so könnte das zuvor betrachtete Wort aBaBaBA außerdem in die Wörter BaBA bzw. aBBA abgeleitet werden. (\varepsilon ist die in der Regel verwendete Notation für das 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 Compilerbaus dazu verwendet, um eine Programmiersprache zu beschreiben. Produktionsregeln werden hier häufig in der Backus-Naur-Form dargestellt.

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