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 V}$ (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}$.