kontekstfrie

Kontekstfrie is an adjective used in Nordic languages meaning "context-free." In formal language theory, it describes grammars and languages whose production rules operate independently of surrounding symbols, so the applicability of a rule depends only on the left-hand side nonterminal.

A context-free grammar (CFG) consists of a finite set of nonterminals, a finite set of terminals, a start symbol, and production rules of the form A → α, where A is a single nonterminal and α is a string of terminals and nonterminals. The context-free property means that the rule choices do not depend on the neighboring characters in the string being formed. CFGs are used to define the syntax of many programming languages, where nested and recursive structures (such as parentheses, blocks, or expressions) are common.

A context-free language is the set of strings that can be derived from the start symbol of a CFG. These languages can be recognized by pushdown automata and are commonly parsed with various strategies, including bottom-up (LR) and top-down (LL) parsing. They are closed under union, concatenation, and the Kleene star, but not under all operations, and they are strictly more expressive than regular languages while not capable of describing certain dependencies that require context-sensitive rules.

Typical examples include the language of balanced parentheses and the language { a^n b^n | n ≥ 0 }. By contrast, languages like { a^n b^n c^n | n ≥ 0 } are not context-free. Context-free grammars form the foundation of many compiler front-ends, enabling syntax analysis, error detection, and tree-based representations of program structure.