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
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.
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- either there is a rule such that and,
- or there exists a string such that and.
The language of a grammar is the set of all strings it generates.
Example
The grammar, with productionsis 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.
Parsing algorithms
Though the expressive power of conjunctive grammarsis greater than those of context-free grammars,
conjunctive grammars retain some of the advantages 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.
Theoretical properties
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.