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 (finite sets of
terminal and nonterminal symbols respectively).
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
V 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 V, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar G.
R is a finite set of productions, each of the form for some in and . The members of R are called the rules or productions of the grammar.
S is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of V.
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 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 u directly yields v, written as , if
either there is a rule such that and ,
or there exists a string such that and .
For any string we say Ggeneratesw, written as , if such that .
The language of a grammar is the set of all strings it generates.
Though the expressive power of conjunctive grammars
is greater than those of context-free grammars,
conjunctive grammars retain some 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,[n 1] inclusion and equivalence.[n 2]
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 (as of 2001).[1]: 533
The expressive power of grammars over a one-letter alphabet has been researched.[citation needed]
This work provided a basis
for the study of
language equations of a more general form.
Synchronized alternating pushdown automata
Aizikowitz and Kaminski[2] introduced a new class of
pushdown automata (PDA) called
synchronized alternating pushdown automata (SAPDA). They proved it to be equivalent to conjunctive grammars in the same way as nondeterministic PDAs are equivalent to context-free grammars.
Notes
^Given a conjunctive grammar, is its generated language empty / finite / regular / context-free?
^Given two conjunctive grammars, is the first's generated language a subset of / equal to the second's?
References
^Alexander Okhotin (2001).
"Conjunctive Grammars"(PDF). Journal of Automata, Languages and Combinatorics. 6 (4): 519–535.
^Aizikowitz, Tamar; Kaminski, Michael (2011). "LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata". Computer Science – Theory and Applications. Lecture Notes in Computer Science. Vol. 6651. pp. 345–358.
doi:
10.1007/978-3-642-20712-9_27.
ISBN978-3-642-20711-2.
ISSN0302-9743.
Alexander Okhotin (2013). "Conjunctive and Boolean grammars: The true general case of the context-free grammars". Computer Science Review. 9: 27–59.
doi:
10.1016/j.cosrev.2013.06.001. This paper supersedes the earlier surveys, "An overview of conjunctive grammars" (Bulletin of the EATCS, 2004) and "Nine open problems for conjunctive and Boolean grammars"