kontextfria

Kontextfria används inom språkvetenskap och datalogi för att beskriva strukturer som inte beror på omgivande sammanhang. Termen används ofta i samband med kontextfri grammatik, kontextfria regler och kontextfria språk. Inom svenska översättningar talas det vanligt om kontextfri grammatik och kontextfria språk.

I formell språkvetenskap definieras en kontextfri grammatik (CFG) av en mängd komponenter: en mängd icke-terminaler N, en mängd terminaler Σ, en startsymbol S och en mängd produktionsregler P. Produktionsreglerna har formen A → α där A ∈ N och α ∈ (N ∪ Σ)*. Det viktiga är att vänsterledet består av en enda icke-terminal och att reglerna inte beror på något sammanhang i omgivningen.

Kontextfria språk kännetecknas av förmågan att uttrycka nestade strukturer som parenteser eller återkommande delsträngar. De kan erkännas av icke-deterministiska pushdown-automater och till viss del av deterministiska pushdown-automater. En enkel kontextfri grammatik för balanserade parenteser illustreras av reglerna: S → SS | ( S ) | ε.

Användningar inkluderar beskrivning av syntax hos många programmeringsspråk och konstruktion av parsers som LL- eller LR-parsers för kompilatorer. Inom lingvistik används kontextfria grammatikregler för vissa strukturer, men naturliga språk kräver ofta mer kraftfulla former för att fånga långväga beroenden och kontextberoende regler.

Historiskt introducerades kontextfri grammatik av Noam Chomsky 1956 som Type-2 i Chomskys hierarki. Begreppet har sedan dess blivit centralt i förståelsen av hur komplexa symbolstrukturer kan genereras och tolkas utan att varje del avsnitt beror på omgivningen.