Productieregel

In een formele grammatica is een productieregel (ook productie of herschrijfregel genoemd) een regel om enkele symbolen te herschrijven naar andere symbolen. Productieregels worden genoteerd met behulp van een pijl, bijvoorbeeld:

$S\rightarrow a$

Het niet-terminale symbool S wordt hier herschreven naar het terminale symbool a. Om productieregels te noteren wordt ook wel gebruikgemaakt van BNF of EBNF.

Deze regels worden productieregels genoemd aangezien ze gebruikt worden om een string te produceren of genereren. De formele grammatica (N, Σ, P, S) met N = {S, A, B}, Σ = {a, b, c} en P = { S → ASB, S → c, A → a, B → b } kan bijvoorbeeld de string "acb" genereren door productieregels herhaaldelijk toe te passen:

$S\Rightarrow ASB\Rightarrow aSB\Rightarrow aSb\Rightarrow acb$

Definitie

Formeel hebben productieregels in P van een formele grammatica (N, Σ, P, S) de volgende vorm:

$(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}$

Vorm van productieregels

In bepaalde soorten grammatica's hebben de productieregels aan een bepaalde vorm, zoals:

• context-vrije grammatica's
• reguliere grammatica's
• context-gevoelige grammatica's