Conjunctive grammar

The rules of a conjunctive grammar are of the form

${\displaystyle A\to {\alpha }_1\mathrm{\&}\dots \mathrm{\&}{\alpha }_m}$

where ${\displaystyle A}$ is a nonterminal and ${\displaystyle {\alpha }_1}$, ..., ${\displaystyle {\alpha }_m}$ are strings formed of symbols in ${\displaystyle \mathrm{\Sigma }}$ and ${\displaystyle V}$ (finite sets of terminal and nonterminal symbols respectively). Informally, such a rule asserts that every string ${\displaystyle w}$ over ${\displaystyle \mathrm{\Sigma }}$ that satisfies each of the syntactical conditions represented by ${\displaystyle {\alpha }_1}$, ..., ${\displaystyle {\alpha }_m}$ therefore satisfies the condition defined by ${\displaystyle A}$.

Formal definition

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

1. V is a finite set; each element ${\displaystyle v\in V}$ 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.
2. Σ 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.
3. R is a finite set of productions, each of the form ${\displaystyle A\to {\alpha }_1\mathrm{\&}\dots \mathrm{\&}{\alpha }_m}$ for some ${\displaystyle A}$ in ${\displaystyle V}$ and ${\displaystyle {\alpha }_i\in (V\cup \mathrm{\Sigma }{)}^{\ast }}$. The members of R are called the rules or productions of the grammar.
4. 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 ${\displaystyle A\to {\alpha }_1\mathrm{\&}\dots \mathrm{\&}{\alpha }_m}$ and ${\displaystyle A\to {\beta }_1\mathrm{\&}\dots \mathrm{\&}{\beta }_n}$ can hence be written as ${\displaystyle A\to {\alpha }_1\mathrm{\&}\dots \mathrm{\&}{\alpha }_m|{\beta }_1\mathrm{\&}\dots \mathrm{\&}{\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.

Definition by derivation

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

• either there is a rule ${\displaystyle A\to {\alpha }_1\mathrm{\&}\dots \mathrm{\&}{\alpha }_m\in R}$ such that ${\displaystyle u=u_{1}A{u}_2}$ and ${\displaystyle v=u_1({\alpha }_1\mathrm{\&}\dots \mathrm{\&}{\alpha }_m)u_2}$,
• or there exists a string ${\displaystyle w\in (V\cup \mathrm{\Sigma }{)}^{\ast }}$ such that ${\displaystyle u=u_1(w\mathrm{\&}\dots \mathrm{\&}w)u_2}$ and ${\displaystyle v=u_{1}w{u}_2}$.

For any string ${\displaystyle w\in {\mathrm{\Sigma }}^{\ast },}$ we say G generates w, written as ${\displaystyle S\stackrel{\ast }{\Rightarrow }w}$, if ${\displaystyle \mathrm{\exists }k\ge 1\mathrm{\exists }{u}_1,\cdots ,u_k\in (V\cup \mathrm{\Sigma }\cup \{\text{“(”},\text{“}\mathrm{\&}\text{”},\text{“)”}\}{)}^{\ast }}$ such that ${\displaystyle S=u_1\Rightarrow u_2\Rightarrow \cdots \Rightarrow u_k=w}$.

The language of a grammar ${\displaystyle G=(V,\mathrm{\Sigma },R,S)}$ is the set of all strings it generates.

Example

The grammar ${\displaystyle G=(\{S,A,B,C,D\},\{a,b,c\},R,S)}$, with productions

${\displaystyle S\to AB\mathrm{\&}DC}$,

${\displaystyle A\to aA|ϵ}$,

${\displaystyle B\to bBc|ϵ}$,

${\displaystyle C\to cC|ϵ}$,

${\displaystyle D\to aDb|ϵ}$,

is conjunctive. A typical derivation is

${\displaystyle S\Rightarrow (AB\mathrm{\&}DC)\Rightarrow (aAB\mathrm{\&}DC)\Rightarrow (aB\mathrm{\&}DC)\Rightarrow (abBc\mathrm{\&}DC)\Rightarrow (abc\mathrm{\&}DC)\Rightarrow (abc\mathrm{\&}aDbC)\Rightarrow (abc\mathrm{\&}abC)\Rightarrow (abc\mathrm{\&}abcC)\Rightarrow (abc\mathrm{\&}abc)\Rightarrow abc}$

It can be shown that ${\displaystyle L(G)=\{a^n{b}^n{c}^n:n\ge 0\}}$. The language is not context-free, proved by the pumping lemma for context-free languages.