Conjunctive grammars

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:

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:

The set of strings over Σ derivable from S in this way is the language generated by the grammar.

These grammars were introduced in the following paper: An up-to-date list of results and the bibliography on conjunctive grammars is given in the following survey paper.

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.