produksjonsregler

Produksjonsregler, i formell grammatikk, er regler som beskriver hvordan symboler i en språkstruktur kan omdannes til andre symboler. En produksjonsregel har formen A → α, der A er et ikke-terminalt symbol og α er en streng av terminale og/eller ikke-terminale symboler. Samlingen av slike regler sammen med et startsymbol S definerer en grammatikk og bestemmer hvilke ordsekvenser som kan genereres.

I lingvistikken og informatikk brukes produksjonsregler til å beskrive syntaksen til språk. I kontekstfri grammatikk (CFG) må venstre side være et enkelt ikke-terminalt symbol, mens høyresiden kan være en blanding av terminaler og ikke-terminaler. Reglene brukes i kompilatorer, parsere og naturlig språkbehandling (NLP). I lingvistikken omtales de ofte som setningsstruktur-regler.

Et eksempel på et lite sett produksjonsregler kan være: S → NP VP; NP → Det N; VP → V NP; Det → en | ei | et; N → hund | katt; V → jager | spiser. Dette kan generere setningen “en hund jager en katt” ved å følge en venstrederivasjon: S → NP VP → Det N VP → Det N V NP → en hund V NP → en hund jager NP → en hund jager en katt.

Produksjonsregler er sentrale i studiet av grammatikk og språk i formell teori. De brukes til å definere grammatiske klasser (for eksempel CFG og andre i Chomskys hierarki) og til å konstruere parse-trær og algoritmer som CYK og Earley for å avgjøre om en streng tilhører språket.