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, P, S), in which:

Σ is the alphabet;
N is the set of nonterminal symbols;
P is the set of rules, each of the form
A -> α₁ & ... & α_m,
where A is a nonterminal and α₁, ..., α_m are strings formed of symbols in Σ and N;
S ∈ N is the start symbol.

Informally, a rule of the above form asserts that every string w over Σ that satisfies each of the syntactical conditions represented by α₁, ..., α_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:

Terms are formed of symbols in Σ and N connected using concatenation and conjunction;
For each rule in P, a subterm A can be rewritten with the term (α₁ & ... & α_m)
A subterm (w & ... & w), for any string w over Σ, can be rewritten with the term w.

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:

A. Okhotin, “Conjunctive grammars” (pdf), Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519-535.

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

A. Okhotin, “Conjunctive and Boolean grammars: the true general case of the context-free grammars” (pdf), manuscript, October 2011.

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.