Produktionsregel

Produktionsregel

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.

Inhaltsverzeichnis

Definition

Formal ist eine Produktionsregel p aus einer Grammatik G = (V,Σ,P,S) mit Vokabular V, Alphabet Σ, 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 α und β, wenn α ein Wort aus V^* \setminus \Sigma^* ist und β ein Wort aus V * ist. Das Wort α 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 β kann dann gemäß der Regel das Wort α ersetzen und kann eine beliebig lange, endliche Folge von Zeichen des Vokabulars sein. Insbesondere kann β auch nur aus Terminalsymbolen bestehen (\beta \in \Sigma^*) oder das leere Wort sein (β = ε).

Eine Regel (α,β) wird oftmals durch die Schreibweise \alpha \rightarrow \beta dargestellt und eine Menge von Regeln \alpha \rightarrow \beta_1,\; \alpha \rightarrow \beta_2,\; \alpha \rightarrow \beta_3, \ldots kann durch die Schreibweise \alpha \rightarrow \beta_1 \;|\; \beta_2 \;|\; \beta_3 \;| \ldots abgekürzt werden.

Anwendung von Produktionsregeln

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

Liegt ein Wort v_1\alpha v_2  = v \in V^+ vor, so lässt sich eine Produktionsregel (α,β) auf v anwenden, mit dem resultierenden Wort v1βv2. 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 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. (ε 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.

Linguistik

In der Theorie der Transformationsgrammatik veranschaulichen Produktionsregeln, die hier Phrasenstrukturregeln (PS-Regeln) genannt werden, den Gedanken, dass ein Satz allmählich durch Umwandlung einer Tiefenstruktur in eine Oberflächenstruktur entstehe.

Die ersten und klassisch gewordenen PS-Regeln in Chomskys Buch "Strukturen der Syntax" 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)

Die zweite Regel illustriert laut Chomsky die Kreativität von Sprache. Mit einer Regel können viele (unendliche) Kombinationen von Texten erzeugt werden. Dies erkläre, warum Kleinkinder noch nie gehörte Sätze sagen können; in einer Universalgrammatik seien diese Regeln nämlich schon angeboren.

Weblinks

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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Produktionsregel — Begriff in der künstlichen Intelligenz für eine ⇡ Regel der Form „wenn Bedingung(en), dann Schlussfolgerung oder Aktion(en)“, wobei sich die Bedingungen auf die Menge der in der ⇡ Wissensbasis gespeicherten bzw. bereits hergeleiteten (⇡ Inferenz) …   Lexikon der Economics

  • Nichtterminale — Formale Grammatiken sind mathematische Modelle von Grammatiken, die mit Hilfe des Semi Thue Systems angegeben werden und durch die formale Sprachen beschrieben und erzeugt werden können. Sie werden in der theoretischen Informatik, insbesondere in …   Deutsch Wikipedia

  • Startsymbol — Formale Grammatiken sind mathematische Modelle von Grammatiken, die mit Hilfe des Semi Thue Systems angegeben werden und durch die formale Sprachen beschrieben und erzeugt werden können. Sie werden in der theoretischen Informatik, insbesondere in …   Deutsch Wikipedia

  • Startvariable — Formale Grammatiken sind mathematische Modelle von Grammatiken, die mit Hilfe des Semi Thue Systems angegeben werden und durch die formale Sprachen beschrieben und erzeugt werden können. Sie werden in der theoretischen Informatik, insbesondere in …   Deutsch Wikipedia

  • SOAR (Kognition) — Soar (früher SOAR als Akronym für State, Operator And Result) ist eine kognitive Architektur; also eine Theorie, die alle primitiven Mechanismen und Strukturen definiert, die menschlicher Kognition zugrunde liegen. Diese primitiven Prinzipien… …   Deutsch Wikipedia

  • Soar (Kognition) — Soar (früher SOAR als Akronym für State, Operator Apply Result) ist eine kognitive Architektur; also eine Theorie, die alle primitiven Mechanismen und Strukturen definiert, die menschlicher Kognition zugrunde liegen. Diese primitiven Prinzipien… …   Deutsch Wikipedia

  • Kontextfreie Grammatiken — Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ 2 Grammatiken der Chomsky Hierarchie. Inhaltsverzeichnis 1 Definition 2 Normalformen 3 Von G erzeugte Sprache 4 Eigenschaften …   Deutsch Wikipedia

  • PS-Regel — Eine Produktionsregel (auch Regel oder Produktion genannt) ist ein geordnetes Paar (P,Q) der beiden Wörter P und Q, welches besagt, dass bei der Erzeugung einer formalen Sprache aus einer gegebenen formalen Grammatik mit dieser Produktionsregel… …   Deutsch Wikipedia

  • Phrasenstrukturregel — Eine Produktionsregel (auch Regel oder Produktion genannt) ist ein geordnetes Paar (P,Q) der beiden Wörter P und Q, welches besagt, dass bei der Erzeugung einer formalen Sprache aus einer gegebenen formalen Grammatik mit dieser Produktionsregel… …   Deutsch Wikipedia

  • Produktion (Grammatik) — Eine Produktionsregel (auch Regel oder Produktion genannt) ist ein geordnetes Paar (P,Q) der beiden Wörter P und Q, welches besagt, dass bei der Erzeugung einer formalen Sprache aus einer gegebenen formalen Grammatik mit dieser Produktionsregel… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”