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 is a nonterminal and ,..., are strings formed of symbols in and . Informally, such a rule asserts that every string over that satisfies each of the syntactical conditions represented by,..., therefore satisfies the condition defined by.
Formal definition
A conjunctive grammar is defined by the 4-tuple where
is a finite set; each element is called a nonterminal symbol or a variable. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories.
is a finite set of terminals, disjoint from, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar.
is a finite set of productions, each of the form for some in and. The members of are called the rules or productions of the grammar.
is the start variable, used to represent the whole sentence. It must be an element of.
It is common to list all right-hand sides for the same left-hand side on the same line, using | to separate them. Rules and can hence be written as. 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.
Definition by derivation
For any strings, we say directly yields, written as, if
For any string we say generates, written as, if such that. The language of a grammar is the set of all strings it generates.
Example
The grammar, with productions is conjunctive. A typical derivation is It can be shown that. The language is not context-free, proved by the pumping lemma for context-free languages.
A property that is undecidable already for context-free languages or finite intersections of them, must be undecidable also for conjunctive grammars; these include: emptiness, finiteness, regularity, context-freeness, The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring. Closure under complement and under ε-free string homomorphism are still open problems. The expressive power of grammars over a one-letter alphabet has been researched. This work provided a basis for the study of language equations of a more general form.
Aizikowitz and Kaminski introduced a new class of pushdown automata called synchronized alternating pushdown automata. They proved it to be equivalent to conjunctive grammars in the same way as nondeterministic PDAs are equivalent to context-free grammars.
