WikiDer > Produktionslinie

In einem formale Grammatik ist ein Fließband (ebenfalls Produktion oder Regel umschreiben genannt) eine Regel, um einige Symbole in andere Symbole umzuschreiben. Produktionslinien sind mit einem Pfeil gekennzeichnet, zum Beispiel:

${displaystyle Visierpfeil a}$

Es nicht-terminales Symbol S wird hier umgeschrieben in die Klemmensymbol a. Um Produktionslinien aufzuzeichnen, wird auch . verwendet BNF oder EBNF.

Diese Regeln werden Produktionsregeln genannt, weil sie verwendet werden, um Schnur zu produzieren oder zu generieren. Die formale Grammatik (Nein, , p, so) mit Nein = {S, A, B}, Σ = {a, b, c} und p Zum Beispiel kann = { S → ASB, S → c, A → a, B → b } den String "acb" durch wiederholtes Anwenden von Produktionsregeln erzeugen:

${displaystyle SRightarrow ASBRrightarrow asSBRrightarrow asSbRightarrow acb}$

Definition

Formal sind Produktionsregeln in p einer formalen Grammatik (Nein, , p, so) folgendes Formular:

${displaystyle (Sigma Tasse N)^{*}N(Sigma Tasse N)^{*}ightarrow (Sigma Tasse N)^{*}}$

Form der Produktionsregeln

In bestimmten Grammatiktypen haben die Produktionsregeln eine bestimmte Form, wie zum Beispiel:

• kontextfreie Grammatiken
• reguläre Grammatiken
• kontextsensitive Grammatiken