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

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

A conjunctive grammar ${\displaystyle G}$ is defined by the 4-tuple ${\displaystyle G=(V,\Sigma ,R,S)}$ where

It is common to list all right-hand sides for the same left-hand side on the same line, using | (the pipe symbol) to separate them. Rules ${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}}$ and ${\displaystyle A\rightarrow \beta _{1}\&\ldots \&\beta _{n}}$ can hence be written as ${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\ |\ \beta _{1}\&\ldots \&\beta _{n}}$.

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.

For any strings ${\displaystyle u,v\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}}$, we say u directly yields v, written as ${\displaystyle u\Rightarrow v\,}$, if

For any string ${\displaystyle w\in \Sigma ^{*},}$ we say G generates w, written as ${\displaystyle S\ {\stackrel {*}{\Rightarrow }}\ w}$, if ${\displaystyle \exists k\geq 1\,\exists \,u_{1},\cdots ,u_{k}\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}}$ such that ${\displaystyle S=\,u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}\,=w}$.