Produktionsregel

in der Theorie formaler Grammatiken eine Regel, die angibt, wie aus Wörtern durch eine Grammatik neue Wörter bzw. Symbolfolgen produziert werden

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

Definition

Bearbeiten

Formal ist eine Produktionsregel   aus einer Grammatik   - mit Vokabular  , Alphabet   von Terminalsymbolen, Regelmenge   und Startsymbol   - ein Element der Regelmenge, also  .[1]

Eine Regel ist ein geordnetes Paar   der beiden Wörter   und  , wenn   ein Wort aus   ist und   ein Wort aus   ist. Das Wort   kann also eine beliebig lange Folge von Zeichen des Vokabulars   sein (  ist die Kleenesche Hülle von  ), solange sie nicht leer ist und nicht nur aus Terminalsymbolen   besteht. Es ist daher   . 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 ( ) oder das leere Wort sein ( ). Damit stellen die Produktionsregeln eine endliche Teilmenge des kartesischen Mengenprodukts

 ,

also eine 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   statt   zu stehen.[2]

Eine Regel   wird oftmals durch die Schreibweise   (mit dem Relationszeichen   anstelle von  ) dargestellt, und zu jedem festen   kann die Gesamtheit zugehöriger Regeln   durch die Schreibweise   abgekürzt werden.[3]

Anwendung von Produktionsregeln

Bearbeiten

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   vor, so lässt sich eine Produktionsregel   auf   anwenden, mit dem resultierenden Wort  . 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

Bearbeiten

Es sei innerhalb einer formalen Grammatik mit den Nichtterminalsymbolen   und den Terminalsymbolen   die Produktionsregel   definiert. Durch Anwendung dieser Regel kann bei der Erzeugung der durch die Grammatik beschriebenen Sprache zum Beispiel das Wort   zum Wort   abgeleitet werden, wobei hier das Präfix   durch die Konklusion   ersetzt wird. Es wäre jedoch nach der Definition formaler Grammatiken auch möglich, das zweite Vorkommen des Wortes   zu ersetzen, so dass das Wort   entsteht.

Wäre außerdem die Regel   definiert, so könnte das zuvor betrachtete Wort   außerdem in die Wörter   bzw.   abgeleitet werden. (  ist die in der Regel verwendete Notation für das leere Wort, ein Wort, das aus keinem einzigen Zeichen besteht.)

Informatik

Bearbeiten

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

Bearbeiten

In der Theorie der Transformationsgrammatik veranschaulichen Produktionsregeln, die hier Phrasenstrukturregeln (PS-Regeln) genannt werden, den Gedanken, dass ein Satz eine grammatische Struktur besitzt, die aus kategorietragenden Bestandteilen rekursiv aufgebaut ist. Die ersten und klassisch gewordenen PS-Regeln in Noam Chomskys 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

Bearbeiten
  1. Die Mitglieder der Menge   bezeichnet man als Nichtterminalzeichen, zu diesen gehört das Startzeichen, also  .
  2. Sinngemäß nach Klaus Reinhardt: Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen, Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994.
  3. Vergleiche Backus-Naur-Form.
Bearbeiten
Wiktionary: Phrasenstrukturregel – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen