Conjunctive grammars, introduced by Okhotin in 2000, are an extension of context-free grammars, in which the rules may contain a conjunction operation. Besides explicit conjunction, conjunctive grammars allow implicit disjunction represented by multiple rules for a single nonterminal, which is the only logical operation expressible in context-free grammars. Conjunction can be used, in particular, to specify intersection of languages. A further extension of conjunctive grammars known as Boolean grammars additionally allows explicit negation.
Though the expressive means of conjunctive grammars are greater than those of context-free grammars, they retain some practically useful properties of the latter, such as efficient parsing algorithms.
A conjunctive grammar is defined as a quadruple (Σ, N, R, S), in which:
A → α1 & ... & αm,where A ∈ N, m ≥ 1 and α1, ..., αm are strings formed of symbols in Σ and N;
Informally, a rule of the above form asserts that every string w over Σ that satisfies each of the syntactical conditions represented by α1, ..., αm therefore satisfies the condition defined by A. Two equivalent formal definitions of the language specified by a conjunctive grammar exist. One definition is based upon representing the grammar as a system of language equations with union, intersection and concatenation and considering its least solution. The other definition generalizes Chomskian derivation to term rewriting of the following form:
There are awards offered for solving a few theoretical problems on conjunctive grammars.
Last updated: 9 October, 2011. Written a new survey of conjunctive and Boolean grammars.