# Conjunctive grammar

Conjunctive grammars are a class of formal grammars studied in formal language theory. They extend the basic type of grammars, the context-free grammars, with a conjunction operation. Besides explicit conjunction, conjunctive grammars allow implicit disjunction represented by multiple rules for a single nonterminal symbol, which is the only logical connective 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.

The rules of a conjunctive grammar are of the form

${\displaystyle A\to \alpha _{1}\And \ldots \And \alpha _{m}}$

where ${\displaystyle A}$ is a nonterminal and ${\displaystyle \alpha _{1}}$, ..., ${\displaystyle \alpha _{m}}$ are strings formed of symbols in ${\displaystyle \Sigma }$ and ${\displaystyle N}$ (finite sets of terminal and nonterminal symbols respectively). Informally, such a rule asserts that every string ${\displaystyle w}$ over ${\displaystyle \Sigma }$ that satisfies each of the syntactical conditions represented by ${\displaystyle \alpha _{1}}$, ..., ${\displaystyle \alpha _{m}}$ therefore satisfies the condition defined by ${\displaystyle 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 Chomsky's generative definition of the context-free grammars using rewriting of terms over conjunction and concatenation.

Though the expressive means of conjunctive grammars are greater than those of context-free grammars, conjunctive grammars retain some practically useful properties of the latter. Most importantly, there are generalizations of the main context-free parsing algorithms, including the linear-time recursive descent, the cubic-time generalized LR, the cubic-time Cocke-Kasami-Younger, as well as Valiant's algorithm running as fast as matrix multiplication.

A number of theoretical properties of conjunctive grammars have been researched, including the expressive power of grammars over a one-letter alphabet and numerous undecidable decision problems. This work provided a basis for the study language equations of a more general form.

## References

• Alexander Okhotin, Conjunctive grammars. Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519-535. (pdf)
• Alexander Okhotin, An overview of conjunctive grammars. In: Gheorghe Paun, Grzegorz Rozenberg, Arto Salomaa (Eds.), Current Trends in Theoretical Computer Science: The Challenge of the New Century, Vol. 2, World Scientific, 2004, 545--566. (pdf)
• Artur Jeż. Conjunctive grammars can generate non-regular unary languages. International Journal of Foundations of Computer Science 19(3): 597-615 (2008) Technical report version (pdf)